https://judge.telerikacademy.com/problem/29largestareamatrix Это упражнение.Напишите программу, которая находит наибольшую площадь равных соседних элементов в прямоугольной матрице и печатает ее размер.Ввод
В первой строке вы получите числа N и M, разделенные одним пробелом. В следующих N строках будет M чисел, разделенных пробелами - элементы матрицы
Выходные данные
Печать размера наибольшей области равных соседних элементов
Ограничения
3 <= N, M <= 1024 Ограничение времени: 0,5 с для JAVA Ограничение памяти: 50 МБ</p>
И это мое решение.
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static class Node {
private int rowIndex, colIndex;
Node(int rowIndex, int colIndex) {
this.rowIndex = rowIndex;
this.colIndex = colIndex;
}
Node[] getNeighbourNodes(int maxRowIndex, int maxColIndex) {
Node[] nodes = new Node[4];
int[][] indexesToCheck = {
{rowIndex - 1, colIndex},
{maxRowIndex - 1, colIndex},
{rowIndex + 1, colIndex},
{0, colIndex},
{rowIndex, colIndex - 1},
{rowIndex, maxColIndex - 1},
{rowIndex, colIndex + 1},
{rowIndex, 0}
};
for (int i = 0; i < indexesToCheck.length; i += 2) {
int rowIndex = indexesToCheck[i][0], backupRowIndex = indexesToCheck[i + 1][0];
int colIndex = indexesToCheck[i][1], backupColIndex = indexesToCheck[i + 1][1];
if (indexExists(rowIndex, colIndex, maxRowIndex, maxColIndex)) {
nodes[i / 2] = new Node(rowIndex, colIndex);
} else {
nodes[i / 2] = new Node(backupRowIndex, backupColIndex);
}
}
return nodes;
}
private boolean indexExists(int row, int col, int maxRowIndex, int maxColIndex) {
return row >= 0 && col >= 0 && row < maxRowIndex && col < maxColIndex;
}
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int m = keyboard.nextInt();
int[][] matrix = new int[n][m];
boolean[][] visitedElements = new boolean[n][m];
for (int row = 0; row < n; row++) {
for (int col = 0; col < m; col++) {
matrix[row][col] = keyboard.nextInt();
}
}
int maxCounter = 0;
for (int row = 0; row < n; row++) {
for (int col = 0; col < m; col++) {
if (!visitedElements[row][col]) {
maxCounter = Math.max(maxCounter, countAreaInMatrixDFS(row, col, matrix, visitedElements, n, m));
}
}
}
System.out.println(maxCounter);
}
private static int countAreaInMatrixDFS(int row, int col, int[][] matrix, boolean[][] visitedElements, int maxRowIndex, int maxColIndex) {
Stack<Node> stack = new Stack<>();
stack.push(new Node(row, col));
visitedElements[row][col] = true;
int counter = 1;
while (stack.size() > 0) {
Node currentNode = stack.pop();
row = currentNode.rowIndex;
col = currentNode.colIndex;
Node[] neighboursIndexes = currentNode.getNeighbourNodes(maxRowIndex, maxColIndex);
for (Node node : neighboursIndexes) {
if (!visitedElements[node.rowIndex][node.colIndex] && matrix[row][col] == matrix[node.rowIndex][node.colIndex]) {
stack.push(node);
visitedElements[node.rowIndex][node.colIndex] = true;
counter++;
}
}
}
return counter;
}
}
Я пытался без класса Node и с BufferedReader, и я все еще получаю исключение ограничения по времени.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] firstLine = br.readLine().split(" ");
int n = Integer.parseInt(firstLine[0]);
int m = Integer.parseInt(firstLine[1]);
int[][] matrix = new int[n][m];
boolean[][] visitedElements = new boolean[n][m];
for (int row = 0; row < n; row++) {
String[] line = br.readLine().split("\\s");
matrix[row] = Arrays.stream(line).mapToInt(Integer::parseInt).toArray();
}
int maxCounter = 0;
for (int row = 0; row < n; row++) {
for (int col = 0; col < m; col++) {
if (!visitedElements[row][col]) {
maxCounter = Math.max(maxCounter, countAreaInMatrixDFS(row, col, matrix, visitedElements, n, m));
}
}
}
System.out.println(maxCounter);
}
private static int countAreaInMatrixDFS(int row, int col, int[][] matrix, boolean[][] checkedElements, int maxRowIndex, int maxColIndex) {
Stack<Integer[]> stack = new Stack<>();
stack.push(new Integer[]{row, col});
checkedElements[row][col] = true;
int counter = 1;
while (stack.size() > 0) {
Integer[] elementIndexes = stack.pop();
row = elementIndexes[0];
col = elementIndexes[1];
int[][] neighboursIndexes = getNeighbourNodes(row, col, maxRowIndex, maxColIndex);
for (int[] indexes : neighboursIndexes) {
int neighbourRow = indexes[0];
int neighbourCol = indexes[1];
if (!checkedElements[neighbourRow][neighbourCol] && matrix[row][col] == matrix[neighbourRow][neighbourCol]) {
stack.push(new Integer[]{neighbourRow, neighbourCol});
checkedElements[neighbourRow][neighbourCol] = true;
counter++;
}
}
}
return counter;
}
private static int[][] getNeighbourNodes(int rowIndex, int colIndex, int maxRowIndex, int maxColIndex) {
int[][] indexes = new int[4][];
if (indexExists(rowIndex - 1, colIndex, maxRowIndex, maxColIndex)) {
indexes[0] = new int[]{rowIndex - 1, colIndex};
} else {
indexes[0] = new int[]{maxRowIndex - 1, colIndex};
}
if (indexExists(rowIndex + 1, colIndex, maxRowIndex, maxColIndex)) {
indexes[1] = new int[]{rowIndex + 1, colIndex};
} else {
indexes[1] = new int[]{0, colIndex};
}
if (indexExists(rowIndex, colIndex - 1, maxRowIndex, maxColIndex)) {
indexes[2] = new int[]{rowIndex, colIndex - 1};
} else {
indexes[2] = new int[]{rowIndex, maxColIndex - 1};
}
if (indexExists(rowIndex, colIndex + 1, maxRowIndex, maxColIndex)) {
indexes[3] = new int[]{rowIndex, colIndex + 1};
} else {
indexes[3] = new int[]{rowIndex, 0};
}
return indexes;
}
private static boolean indexExists(int row, int col, int maxRowIndex, int maxColIndex) {
return row >= 0 && col >= 0 && row < maxRowIndex && col < maxColIndex;
}
}