java - 在二维数组中找到最长的路径(如多米诺骨牌)

Question

<分区>

Answer 1

你的深度优先搜索的问题似乎是你计算你访问的每个领域。不管该字段是否是最长路径的一部分。

因此，如果您像这样更改代码，它应该可以工作:

public class Main {

    static int totalRows = 4;
    static int totalCols = 6;
    static int[] rowNbr = {1, -1, 0, 0};
    static int[] colNbr = {0, 0, 1, -1};
    //static int count = 0; //count is no longer needed
    static boolean[][] visited = new boolean[4][6];

    public static void main(String[] args) {
        int mat[][] = {{1, 0, 0, 0, 0, 0}, //
                {1, 1, 1, 1, 1, 0}, //
                {1, 0, 0, 0, 0, 0}, //
                {1, 0, 0, 0, 0, 0}};

        int maxDepth = dfs(mat, 0, 0, 1);
        System.out.println(maxDepth);

        //test second row {1, 1, 0, 0, 0, 0} like Damien mentioned
        mat = new int[][] {{1, 0, 0, 0, 0, 0}, //
                {1, 1, 0, 0, 0, 0}, //
                {1, 0, 0, 0, 0, 0}, //
                {1, 0, 0, 0, 0, 0}};
        visited = new boolean[4][6];

        maxDepth = dfs(mat, 0, 0, 1);
        System.out.println(maxDepth);

        //test a loop
        mat = new int[][] {{1, 0, 0, 0, 0, 0}, //
                {1, 1, 1, 1, 1, 0}, //
                {1, 0, 0, 0, 1, 0}, //
                {1, 1, 1, 1, 1, 0}};
        visited = new boolean[4][6];

        maxDepth = dfs(mat, 0, 0, 1);
        System.out.println(maxDepth);

        //test problem case
        mat = new int[][] {{1, 0, 1, 1, 0, 0}, //
                {1, 1, 1, 1, 1, 1}, //
                {1, 0, 0, 0, 0, 1}, //
                {1, 0, 0, 0, 0, 0}};
        visited = new boolean[4][6];

        maxDepth = dfs(mat, 0, 0, 1);
        System.out.println(maxDepth);
    }

    static int dfs(int[][] matrix, int startRow, int startCol, int depth) {//added a parameter for the recursion depth here
        visited[startRow][startCol] = true;
        int maxDepth = depth;//the maximum depth is the current recursion depth (until you find a deeper one)
        for (int k = 0; k < 4; k++) {
            int row1 = startRow + rowNbr[k];
            int col1 = startCol + colNbr[k];
            if (isValid(row1, col1)) {
                if (!visited[row1][col1] && matrix[row1][col1] == 1) {
                    int newDepth = dfs(matrix, row1, col1, depth + 1);//find the next cell in the path
                    if (newDepth > maxDepth) {//if the path is deeper than the deepest known path update the length
                        maxDepth = newDepth;
                    }
                }
            }
        }
        return maxDepth;
    }

    static boolean isValid(int row, int col) {
        if (row < 0 || row > totalRows - 1)
            return false;
        if (col < 0 || col > totalCols - 1)
            return false;
        return true;
    }
}

此代码在递归中找到最深路径，并且仅在新长度大于当前最长路径时才更新最大长度。

它仍然使用深度优先搜索。我添加了更多测试用例以证明它适用于所有输入字段:

第一个测试用例是您在问题中提供的测试:

int mat[][] = {{1, 0, 0, 0, 0, 0}, //
                {1, 1, 1, 1, 1, 0}, //
                {1, 0, 0, 0, 0, 0}, //
                {1, 0, 0, 0, 0, 0}};

输出是6，这似乎是正确的。

第二个测试是评论中提到的测试用例Damien:

//test second row {1, 1, 0, 0, 0, 0} like Damien mentioned
mat = new int[][] {{1, 0, 0, 0, 0, 0}, //
        {1, 1, 0, 0, 0, 0}, //
        {1, 0, 0, 0, 0, 0}, //
        {1, 0, 0, 0, 0, 0}};
visited = new boolean[4][6];//reset visited for the next test

这里的输出是 4，这似乎是正确的(因为深度优先搜索在这种情况下它仍然有效)。

第三个测试是一个循环:

//test a loop
mat = new int[][] {{1, 0, 0, 0, 0, 0}, //
        {1, 1, 1, 1, 1, 0}, //
        {1, 0, 0, 0, 1, 0}, //
        {1, 1, 1, 1, 1, 0}};
visited = new boolean[4][6];

输出为 13。仍然正确。

第四个测试是一个测试用例，我认为它会有问题，但它似乎也有效:

//test problem case
mat = new int[][] {{1, 0, 1, 1, 0, 0}, //
        {1, 1, 1, 1, 1, 1}, //
        {1, 0, 0, 0, 0, 1}, //
        {1, 0, 0, 0, 0, 0}};
visited = new boolean[4][6];

输出为10，也是正确的。

需要更多的测试来验证它对每个输入都有效，但对于大多数输入它都有效。