Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Collections;
- import java.util.Scanner;
- public class SmallWorldDSA {
- static int row, col;
- static int[][] matrix;
- static boolean[][] isVisited;
- static int currentRep;
- public static void main(String[] args) {
- Scanner scanner = new Scanner(System.in);
- String[] input = scanner.nextLine().split(" ");
- row = Integer.parseInt(input[0]);
- col = Integer.parseInt(input[1]);
- matrix = new int[row][col];
- isVisited = new boolean[row][col];
- ArrayList<Integer> allRepetitions = new ArrayList<>();
- for (int i = 0; i < row; i++) {
- String[] columns = scanner.nextLine().split("");
- for (int j = 0; j < col; j++) {
- matrix[i][j] = Integer.parseInt(columns[j]);
- }
- }
- for (int i = 0; i < matrix.length; i++) {
- for (int j = 0; j < matrix[0].length; j++) {
- if (matrix[i][j] != 1) {
- isVisited[i][j] = true;
- }
- else {
- currentRep = calculateRepetition(matrix, i, j, matrix[i][j]);
- if(currentRep==0){
- continue;
- }
- allRepetitions.add(currentRep);
- }
- }
- }
- Collections.sort(allRepetitions);
- Collections.reverse(allRepetitions);
- for (Integer n : allRepetitions) {
- System.out.println(n);
- }
- }
- public static int calculateRepetition(int[][] matrix, int row, int col, int currentNumber) {
- if (isInvalid(row, col) || matrix[row][col] != currentNumber || isVisited[row][col]) {
- return 0;
- }
- int countNumbers = 1;
- isVisited[row][col] = true;
- countNumbers += calculateRepetition(matrix, row - 1, col, currentNumber);
- countNumbers += calculateRepetition(matrix, row + 1, col, currentNumber);
- countNumbers += calculateRepetition(matrix, row, col - 1, currentNumber);
- countNumbers += calculateRepetition(matrix, row, col + 1, currentNumber);
- return countNumbers;
- }
- public static boolean isInvalid(int row, int col) {
- return row<0 || row>=matrix.length || col<0 || col>=matrix[0].length;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment