sunfresh

SmallWorld

Jan 30th, 2023
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.36 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.Scanner;
  4.  
  5. public class SmallWorldDSA {
  6. static int row, col;
  7. static int[][] matrix;
  8. static boolean[][] isVisited;
  9.  
  10. static int currentRep;
  11.  
  12. public static void main(String[] args) {
  13.  
  14. Scanner scanner = new Scanner(System.in);
  15. String[] input = scanner.nextLine().split(" ");
  16.  
  17. row = Integer.parseInt(input[0]);
  18. col = Integer.parseInt(input[1]);
  19.  
  20. matrix = new int[row][col];
  21. isVisited = new boolean[row][col];
  22. ArrayList<Integer> allRepetitions = new ArrayList<>();
  23.  
  24. for (int i = 0; i < row; i++) {
  25. String[] columns = scanner.nextLine().split("");
  26. for (int j = 0; j < col; j++) {
  27. matrix[i][j] = Integer.parseInt(columns[j]);
  28. }
  29. }
  30. for (int i = 0; i < matrix.length; i++) {
  31. for (int j = 0; j < matrix[0].length; j++) {
  32. if (matrix[i][j] != 1) {
  33. isVisited[i][j] = true;
  34. }
  35. else {
  36. currentRep = calculateRepetition(matrix, i, j, matrix[i][j]);
  37. if(currentRep==0){
  38. continue;
  39. }
  40. allRepetitions.add(currentRep);
  41. }
  42. }
  43. }
  44. Collections.sort(allRepetitions);
  45. Collections.reverse(allRepetitions);
  46. for (Integer n : allRepetitions) {
  47. System.out.println(n);
  48. }
  49. }
  50.  
  51. public static int calculateRepetition(int[][] matrix, int row, int col, int currentNumber) {
  52. if (isInvalid(row, col) || matrix[row][col] != currentNumber || isVisited[row][col]) {
  53. return 0;
  54. }
  55.  
  56. int countNumbers = 1;
  57.  
  58. isVisited[row][col] = true;
  59. countNumbers += calculateRepetition(matrix, row - 1, col, currentNumber);
  60. countNumbers += calculateRepetition(matrix, row + 1, col, currentNumber);
  61. countNumbers += calculateRepetition(matrix, row, col - 1, currentNumber);
  62. countNumbers += calculateRepetition(matrix, row, col + 1, currentNumber);
  63. return countNumbers;
  64. }
  65. public static boolean isInvalid(int row, int col) {
  66. return row<0 || row>=matrix.length || col<0 || col>=matrix[0].length;
  67. }
  68. }
  69.  
Advertisement
Add Comment
Please, Sign In to add comment