对2d数组进行递归遍历以查找唯一路径

Question

我需要遍历一个0的2D数组(代表开放路径)和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布尔图中标记边缘的方式有关,但我不确定.任何帮助将非常感激.

这是我用来测试数组的主要方法,它是一个简单的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种方法可以从墙上到达末尾.