arrays - 二维数组的递归遍历以找到唯一路径

Question

我需要遍历一个由 0(代表开放路径)和 1(代表墙壁)组成的二维数组。我必须计算 NxN 网格从 (0,0) 到 (N-1,N-1) 的唯一路径的数量。我已经编写了一个递归方法来执行此操作，但是我无法弄清楚为什么我的方法的遍历部分(即直线、左和右移动)没有按预期工作:

    public static void TraversePath(int [][] Grid, boolean[][] isTraversed, int column, int row) {
    if(row < 0 || column < 0 || row > Grid[0].length || column > Grid[0].length )
        return; // if you go out of bounds
    if(isTraversed[column][row] == true)
        return; // if you have already been to the point
    if(Grid[column][row]==1) {
        isTraversed[column][row] = true; // if the current point is a wall mark it as traversed
        return;
    }
    if(Grid[column][row]!=1 && (row == Grid[0].length-1 && column == Grid[0].length-1)) { //if you get to an endpoint that isn't a wall
        uniquePaths++; //counter that tallys the unique paths
        isTraversed[column][row] = true;
        return;
    }

    TraversePath(Grid,column,row+1);//Straight
    TraversePath(Grid,column-1, row);//Left
    TraversePath(Grid,column+1, row);//Right

}



public static void main(String[] args) {
    int [][]Grid = new int[][]
            {
        {0,1,1,0},
        {0,0,1,0},
        {0,0,0,0},
        {0,1,1,0}
            };
    boolean[][] isTraversed = new boolean[Grid.length][Grid.length];
    for(int i = 0; i < Grid.length; i++) {
        for(int j = 0; j< Grid.length; j++)
            isTraversed[i][j] = false;
    }
    TraversePath(Grid,isTraversed,0,0);
    System.out.println(uniquePaths);

} 

当我运行这段代码时，我不断收到 StackOverFlow 错误(嘿，听起来很熟悉)。我认为这可能与我如何标记 isTraversed bool 图中访问的边有关，但我不确定。任何帮助将不胜感激。

这是我用来测试数组的主要方法，它是一个简单的 4x4 网格，有 2 条通往 (3,3) 的唯一路径。

Answer 1

你的 Stack Overflow错误是由于您可以连续向左然后再次向右移动而引起的。假设您只能朝正方向移动，您可以使用动态规划制作一个非常简单的递归函数来防止您获得 Stack Overflow。错误。

public static int possiblePaths(int[][] grid, int x,int y,int [][] dp){
    if(x<0||x>=grid.length||y<0||y>=grid[0].length)
        return 0;
    if(dp[x][y]==-1){
        dp[x][y]=possiblePaths(grid,x+1,y,dp)+possiblePaths(grid,x,y+1,dp);
    }
    return dp[x][y];
}

public static void main(String[] args) {
    int [][]Grid = new int[][]
            {
        {0,1,1,0},
        {0,0,1,0},
        {0,0,0,0},
        {0,1,1,0}
            };
    int [][] dp = new int[Grid.length][Grid[0].length];
    for(int i = 0; i < Grid.length; i++) {
        for(int j = 0; j< Grid[0].length; j++)
            if(Grid[i][j]==1)
                dp[i][j]=0;
            else
                dp[i][j]=-1;
    }
    dp[Grid.length-1][Grid[0].length-1]=0;
    System.out.println(possiblePaths(Grid,0,0,dp));

} 

这基本上说明了从 (x,y) 获取的方式数量到最后是来自(x+1,y)的路径#的总和和来自 (x,y+1) 的路径数并在 dp(动态编程)数组中记住这些数字，因此您不需要重新计算它们。在 dp 数组中，有墙的单元格被设置为 0，因为从墙到尽头的方法有 0 种。