查找两个单元格之间的路由数

Question

这里的练习是：我需要编写一个递归方法，它可以得到N*N大小的正整数矩阵，起始单元格行和列索引以及结束单元格行和列html" target="_blank">索引，并且该方法需要返回从起始单元格到结束单元格的可能路径数，这些约束条件是：a.你可以从当前位置移动到左单元格、右单元格、上单元格或下单元格。b.你不能越过主对角线，但是你可以转到对角线上的单元格（但不能越过它）。路由中的每个单元格只出现一次。d.矩阵需要像原始矩阵一样，末尾有原始单元格值

到目前为止我得到的是：

public static int numPaths (int[][] mat,int x1, int y1, int x2, int y2){
        if(x1>y1 || x2>y2 || y1<x1 || y2<x2) return 0;
        return numPaths(mat ,x1, y1, x2, y2, x1, y1);
    }
    public static int numPaths (int[][] mat ,int x1, int y1, int x2, int y2, int row, int col){
        if(row<0 || col <0 || row>=mat.length || col>=mat.length ) return 0;
        if(row==x2 && col==y2){ 
            return 1;
        }
        if(row==col){ 
            return numPaths ( mat ,x1, y1, x2, y2, row, col+1) + numPaths( mat ,x1, y1, x2, y2, row-1,col);

        }
        else{
            return numPaths( mat ,x1, y1, x2, y2, row, col+1) + numPaths( mat ,x1, y1, x2, y2, row+1, col)+
                    numPaths( mat ,x1, y1, x2, y2, row-1, col) + numPaths( mat ,x1, y1, x2, y2, row, col-1);    
            }

        }

但我得到堆栈溢出错误，因为我不能使差异，当我访问的细胞之前。我确信在递归方法中有一种方法可以改变单元格中的值，并在以后使其恢复正常，但我想不出一种方法如何做到这一点。

请告知

Answer 1

如果您打算使用矩阵来存储单元格是否已被访问，那么最好将其设置为布尔矩阵。然后在递归之前将值设置为true，然后在递归之后设置为false。

类似下面的方法应该会起作用。我将变量移到类中，因为似乎没有必要传递它们。

比如：

private final int size;
private final boolean visited[][] = new boolean[size][size];

public int numPaths(int x, int y) {
    if (visited[x][y] || x < 0 || y < 0 || x >= size || y >= size)
        return 0;
    if (x == size - 1 && y == size - 1)
        return 1;
    visited[x][y] = true;
    int numPaths = 0;
    numPaths += numPaths(x - 1, y) + numPaths(x, y - 1);
    if (x != y)
        numPaths += numPaths(x + 1, y) + numPaths(x, y + 1;
    visited[x][y] = false;
    return numPaths;
}