java - 查找两个单元格之间的路线数

Question

这是练习:我需要编写递归方法，该方法获取具有 n*n 大小的正整数的矩阵、起始单元格行和列索引以及结束单元格行和列索引，并且该方法需要返回具有以下约束的从起始单元格到结束单元格的可能路线数:a.您可以从当前位置移动到左单元格、右单元格、上单元格或下单元格b.你不能穿过主对角线，但你可以转到对角线上的单元格(但不能穿过它)。c. route 的每个单元仅出现一次。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

如果您打算使用矩阵来存储单元格是否已被访问，那么最好将其设为 boolean 矩阵。然后，只需在递归之前将值设置为 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;
}