java - 查找矩阵中是否存在路径

Question

我必须生成一个随机值为 0 和 1 的 5 x 5 矩阵。

在这样的矩阵中，我必须找到是否存在从左到右由 1 组成的路径。相邻的 1 可以垂直、水平或对角线相邻(也称为 8-连接)。

成功场景的一个例子是

1 0 0 1 0 
0 1 0 1 1 
1 1 1 1 0 
0 0 0 1 0 
1 1 0 1 1 

我已经生成了矩阵，但发现很难确定路径。

我想检查每个上/下/右/对角线索引的值 = 1 并继续。但在这种情况下，我不知道如何维护一条路径。

任何解决方案/算法都会非常有帮助。

Answer 1

编辑: 编辑修复了先前代码中的错误。本质上，它会跟踪以前访问过的节点以避免回溯，并在所有方向上搜索可能的进一步路径。

使用访问过的节点，它还跟踪实际遍历的路径。

public static boolean hasPathHelper(int[][] m, int[][] v, int i, int j){
    if(i < 0 || j < 0 || i >= m.length || j >= m[0].length || v[i][j] >= 0)
        return false;                        // Index out of bounds

    v[i][j] = 0;                             // Mark as visited
    if(m[i][j] == 0)                         // Path stops here
        return false;
    if(j == m[0].length - 1 ||               // Right side reached!
       hasPathHelper(m, v, i - 1, j + 1) ||  // Check upper right
       hasPathHelper(m, v, i + 1, j + 1) ||  // Check lower right
       hasPathHelper(m, v, i + 1, j - 1) ||  // Check lower left
       hasPathHelper(m, v, i + 1, j - 1) ||  // Check upper left
       hasPathHelper(m, v, i + 1, j    ) ||  // Check down
       hasPathHelper(m, v, i - 1, j    ) ||  // Check up
       hasPathHelper(m, v, i    , j + 1) ||  // Check right
       hasPathHelper(m, v, i    , j - 1)     // Check left
    ) v[i][j] = 1;                           // Mark as good path

    return v[i][j] == 1;
}

public static boolean hasPath(int[][] m, int[][] v){
    for(int i = 0; i < m.length; i++)
        if(hasPathHelper(m, v, i, 0))
            return true;

    return false;
}

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

    int[][] v = new int[5][5];                         // v => -1, not visited
    for(int i=0; i<5; i++)                             // v =>  0, visited bad path
        Arrays.fill(v[i], -1);                         // v =>  1, visited good path

    System.out.println("Has Path?: " + hasPath(m, v));
    System.out.println("Path Matrix: ");
    for(int i = 0; i < v.length; i++)
        System.out.println(Arrays.toString(v[i]));    
}

---

输出

Has Path?: true
Path Matrix: 
[ 0,  1,  1, -1,  0]
[ 1,  0,  0,  1, -1]
[-1, -1,  1, -1,  0]
[-1,  1,  0,  0,  0]
[-1, -1,  1,  1,  1]