sunfresh

Largest Surface

Jan 23rd, 2023
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.69 KB | None | 0 0
  1. Largest Surface
  2. Description
  3. Write a program that finds the largest possible sequence of equal neighboring elements in a rectangular matrix and prints its size.
  4.  
  5. Input
  6. On the first line you will receive the numbers N and M separated by a single space;
  7. On the next N lines there will be M numbers separated with spaces - the elements of the matrix;
  8. Output
  9. Print the size of the largest area of equal neighboring elements
  10. Constraints
  11. 3 <= N, M <= 1024
  12. Sample tests
  13. Input
  14. 5 6
  15. 1 3 2 2 2 4
  16. 3 3 3 2 4 4
  17. 4 3 1 2 3 3
  18. 4 3 1 3 3 1
  19. 4 3 3 3 1 1
  20. Output
  21. 13
  22.  
  23. import java.util.Scanner;
  24.  
  25. public class LargestSurface {
  26. static int rows, cols;
  27. static int[][] matrix;
  28. static boolean[][] isVisited;
  29. static int maxSequence = 0;
  30.  
  31. public static void main(String[] args) {
  32. Scanner scanner = new Scanner(System.in);
  33. String inputLine = scanner.nextLine();
  34. String[] inputStringArr = inputLine.split(" ");
  35. rows = Integer.parseInt(inputStringArr[0]);
  36. cols = Integer.parseInt(inputStringArr[1]);
  37. matrix = new int[rows][cols];
  38. isVisited = new boolean[rows][cols];
  39.  
  40. for (int i = 0; i < rows; i++) {
  41. for (int j = 0; j < cols; j++) {
  42. matrix[i][j] = scanner.nextInt();
  43. }
  44. }
  45. System.out.println(getMaxSequence());
  46. }
  47. public static int calculateSurface(int[][] matrix, int row, int col, int currentNumber) {
  48. if (isValid(row, col)) {
  49. return 0;
  50. }
  51. if (isVisited(row, col, currentNumber)) {
  52. return 0;
  53. }
  54. int countNumbers = 1;
  55.  
  56. isVisited[row][col] = true;
  57. countNumbers += calculateSurface(matrix, row - 1, col, currentNumber);
  58. countNumbers += calculateSurface(matrix, row + 1, col, currentNumber);
  59. countNumbers += calculateSurface(matrix, row, col - 1, currentNumber);
  60. countNumbers += calculateSurface(matrix, row, col + 1, currentNumber);
  61. return countNumbers;
  62. }
  63.  
  64. public static boolean isValid(int row, int col) {
  65. return row < 0 || row >= rows || col < 0 || col >= cols;
  66. }
  67. public static boolean isVisited(int row, int col, int currentNumber) {
  68. return isVisited[row][col] || matrix[row][col] != currentNumber;
  69. }
  70. public static int getMaxSequence() {
  71. maxSequence = 0;
  72. for (int i = 0; i < rows; i++) {
  73. for (int j = 0; j < cols; j++) {
  74. if (!isVisited[i][j]) {
  75. int surface = calculateSurface(matrix, i, j, matrix[i][j]);
  76. maxSequence = Math.max(surface, maxSequence);
  77. }
  78. }
  79. }
  80. return maxSequence;
  81. }
  82. }
Advertisement
Add Comment
Please, Sign In to add comment