https://judge.telerikacademy.com/problem/29largestareamatrix 这就是练习。编写一个程序,找出矩形矩阵中相等相邻元素的最大面积并打印其大小。输入
在第一行,您将收到由一个空格分隔的数字 N 和 M 在接下来的 N 行中,将有 M 个用空格分隔的数字 - 矩阵的元素
输出
打印相等相邻元素的最大区域的大小
约束
3 <= N, M <= 1024 时间限制:0.5s for JAVA 内存限制:50MB
这是我的解决方案。
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;
}
}