在二维数组中找到最长的路径（如多米诺骨牌）

Question

我需要从某个点找到最长的路径（就像多米诺骨牌），它可以在文件中显示：

所以我可以创建的从单元格 (0,0) 到 (1,4) 点的最长多米诺骨牌是到 (1,4) 点，而不是到 (3,0) 点。

我已经尝试用 dfs 解决这个问题，并且找到了整个区域的大小 - 我不知道如何更改此代码来计算多米诺骨牌的最长路径。

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;
    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}};

        dfs(mat, 0, 0);
        System.out.println(count);
    }

    static void dfs(int[][] matrix, int startRow, int startCol) {    
        visited[startRow][startCol] = true;
        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) {
                    count++;
                    dfs(matrix, row1, col1);
                }
            }
        }
    }

    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;
    }
}

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，也是正确的。

需要更多的测试来验证它适用于每个输入，但对于大多数输入它都会起作用。

在二维数组中找到最长的路径（如多米诺骨牌）

Find a longest path (like domino) in 2d array

java

algorithm

graph-algorithm