计算在所有 4 个方向上移动的矩阵中从源到目的地的路径

Question

说，我有一个大小为 n*n 的矩阵，如果允许我在所有四个方向上移动，我想从 0,0 遍历到 n-1,n-1 - right、left、up 和 down。如何使用递归查找所有路径。

以下是我执行此操作的方法，因为您只能在两个方向上移动 - right 和 down。

static int findWays2directions( int[][] a, int i, int j ) {
        if ( i < 0 || j < 0 || i == a.length || j == a[0].length )
            return 0;

        if ( i == a.length - 1 && j == a[0].length - 1 )
            return 1;

        int right = findWays2directions( a, i, j + 1 );
        int down = findWays2directions( a, i + 1, j );
        return right + down;
    }

然而，当允许在所有四个方向上移动时，如果我要将额外的递归步骤添加到 left 和 up，这将不起作用。这是因为会产生循环，例如从 0,1 到 0,0 然后回到 0,0 导致无限循环。我试图通过维护一个 visited 二维数组来避免这种情况，如果已经访问过则返回 0 。但是，我认为这不会给我正确的输出，因为问题是计算路径，而不仅仅是遍历。

static int findWays4directions( int[][] a, int i, int j, boolean[][] visited ) {
        if ( i < 0 || j < 0 || i == a.length || j == a[0].length )
            return 0;

        if ( i == a.length - 1 && j == a[0].length - 1 )
            return 1;

        if ( visited[i][i] == true )
            return 0;

        visited[i][j] = true;

        int right = findWays4directions( a, i, j + 1, visited );
        int down = findWays4directions( a, i + 1, j, visited );
        int left = findWays4directions( a, i, j - 1, visited );
        int up = findWays4directions( a, i - 1, j, visited );

        return left + down + right + up;
    }

我如何计算在所有 4 个方向上移动的矩阵中从源到目的地的所有路径

Answer 1

尝试在退出单元格时设置 visited[i][j] = false。但要注意：这不是动态规划解决方案（我确信没有针对此问题的 DP 解决方案）。相反，您正在进行无限搜索（一种回溯）：

另外：修复了代码中的错误 if (visited[i][i]) ...。

static int findWays4directions( int[][] a, int i, int j, boolean[][] visited ) {
    if ( i < 0 || j < 0 || i == a.length || j == a[0].length )
        return 0;

    if ( i == a.length - 1 && j == a[0].length - 1 )
        return 1;

    if ( visited[i][j] == true )
        return 0;

    visited[i][j] = true;

    int right = findWays4directions( a, i, j + 1, visited );
    int down = findWays4directions( a, i + 1, j, visited );
    int left = findWays4directions( a, i, j - 1, visited );
    int up = findWays4directions( a, i - 1, j, visited );

    visited[i][j] = false;

    return left + down + right + up;
}

Answer 2

同意dfs算法，但是base case检查需要添加visited[i][j]来检查重复访问。

if (i < 0 || i >= n || j < 0 || j >= n || visited[i][j]) {
            return 0;
}

计算在所有 4 个方向上移动的矩阵中从源到目的地的路径

count paths from source to destination in a matrix moving in all 4 directions

algorithm

recursion

maze

dynamic-programming

graph-algorithm