Advertisement
Hey_Donny

SmallWorld

Jun 14th, 2022
20
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.57 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.Scanner;
  4.  
  5. public class SmallWorldTwo {
  6. public static ArrayList<Integer> list = new ArrayList<>();
  7.  
  8. public static void main(String[] args) {
  9.  
  10. Scanner scanner = new Scanner(System.in);
  11.  
  12. String[] input = scanner.nextLine().split(" ");
  13.  
  14. int cols = Integer.parseInt(input[0]);
  15. int rows = Integer.parseInt(input[1]);
  16. String[][] matrix = new String[cols][rows];
  17.  
  18. for (int i = 0; i < cols; i++) {
  19. matrix[i] = scanner.nextLine().split("");
  20. }
  21.  
  22. for (int row = 0; row < matrix.length; row++) {
  23. for (int col = 0; col < matrix[row].length; col++) {
  24. if (matrix[row][col].equals("1")) {
  25. list.add(dfs(matrix, row, col));
  26. }
  27. }
  28. }
  29. list.sort(Collections.reverseOrder());
  30. for (Integer integer : list) {
  31. System.out.println(integer);
  32. }
  33. }
  34.  
  35. public static int dfs(String[][] matrix, int row, int col) {
  36. if (row < 0 || col < 0 || row >= matrix.length || col >= matrix[row].length) {
  37. return 0;
  38. }
  39. String position = matrix[row][col];
  40. if (!position.equals("1")) {
  41. return 0;
  42. }
  43. int count = 1;
  44. matrix[row][col] = "0";
  45. count += dfs(matrix, row - 1, col);
  46. count += dfs(matrix, row + 1, col);
  47. count += dfs(matrix, row, col - 1);
  48. count += dfs(matrix, row, col + 1);
  49.  
  50. return count;
  51. }
  52. }
  53.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement