java - 关于寻找矩阵中最大区域的练习的时间限制异常

Question

https://judge.telerikacademy.com/problem/29largestareamatrix 这就是练习。 编写一个程序，找出矩形矩阵中相等相邻元素的最大面积并打印其大小。 输入

在第一行，您将收到由一个空格分隔的数字 N 和 M 在接下来的 N 行中，将有 M 个用空格分隔的数字 - 矩阵的元素

输出

打印等邻元素最大面积的大小

约束

3 <= N, M <= 1024 限时:JAVA 0.5s 内存限制: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;
        }
    }

Answer 1

在这段代码中，

if (!visitedElements[node.rowIndex][node.colIndex] && matrix[row][col] == matrix[node.rowIndex][node.colIndex]) {
    visitedElements[row][col] = true;
    counter++;
    stack.push(node);
}

您正在执行 visitedElements[row][col] = true; 这实际上使当前索引本身再次为真。所以，它的邻居永远不会有机会成为 true 并一直互相添加。因此，它超过了时间限制(因为您的代码看起来很准确)。

将 visitedElements[row][col] = true; 更改为 visitedElements[node.rowIndex][node.colIndex] = true;