优化以使用更少的内存

Question

我编写了一个解决方案，以便找到包含 A-Z 的 M 行和 N 列的矩阵从上到下的路径。 例如，

5 10
ABCDEFGHIJ
ABCDEFGHIJ
ABCDEFGHIJ
ABCDEFGHIJ
YYYYYYYYYJ

从上到下的路径是字符J。

唯一可接受的方向是上、下、左、右。可以有多个路径，然后打印出具有路径的不同字符，相同的字母可以有 2 个或更多路径，如果没有连接第一行和最后一行的路径，则打印出 0

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class generate{
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] dimensions = br.readLine().split(" ");
        int M = Integer.parseInt(dimensions[0]);
        int N = Integer.parseInt(dimensions[1]);

        char[][] matrix = new char[M][N];

        for (int i = 0; i < M; i++) {
            String line = br.readLine();
            matrix[i] = line.toCharArray();
        }

        String result = findPath(matrix, M, N);
        System.out.println(result);
    }

    public static String findPath(char[][] matrix, int M, int N) {
        StringBuilder result = new StringBuilder();
        boolean[][] visited = new boolean[M][N];

        for (int j = 0; j < N; j++) {
            char letter = matrix[0][j];
            if (letter != '.' && !visited[0][j]) {
                if (isConnected(matrix, M, N, 0, j, letter, visited)) {
                    result.append(letter);
                    
                }
            }
        }

        return result.length() > 0 ? result.toString() : "0";
    }

    public static boolean isConnected(char[][] matrix, int M, int N, int x, int y, char target, boolean[][] visited) {
        visited[x][y] = true;

        boolean connected = false;

        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (newX >= 0 && newX < M && newY >= 0 && newY < N
                    && matrix[newX][newY] == target && !visited[newX][newY]) {
                if (newX == M - 1 || isConnected(matrix, M, N, newX, newY, target, visited)) {
                    connected = true;
                }
            }
        }

        return connected;
    }
}

但它使用大量内存，我需要优化它以提高内存效率。

例如，对于大小为 9000x9000 的矩阵，仅 char 数组矩阵就会使用大约 300-400 MB 的内存。

我们如何在整个过程中释放内存或删除矩阵或访问数组中的元素以减少内存使用？

Answer 1

对于矩阵没有太多可做的，因为没有理由相信它首先是可压缩的（可能是随机的）。

但是，值的范围非常有限：仅允许 27 个值。

1. 您可以首先将 16 位

   char

   类型替换为

   byte

   。这将使您的数据使用量减半。
2. 您可以使用小写字母而不是大写字母来将位置标记为已访问，而不是使用侧面数组。这将使您的内存使用量再次减半。

希望这有帮助！