java - 在数组递归中计算从一个点到另一个点的路径，而不重复单元格

Question

当我可以从每个单元格(在数组边界内)向右、向左、向下或向上移动时，我需要计算从一个单元格到另一个单元格的路径数。

在检查路径时，如何避免重复已经经过的单元格？还有另一条规则:

You can't use another array, loops and static variables.

我怎样才能从这里继续？

我的递归函数:

public static int calcPath(int [][] a, int currentx, int currenty, int destx, int desty)
{
    if (currentx == destx && currenty == desty)
        return 1;
    if(!bounds(a,currentx,currenty)) // if the cell isnt in the array bounds
        return 0;

    return  calcPath(math,currentx+1,currenty,destx,desty) +
             calcPath(math,currentx-1,currenty,destx,desty)+
              calcPath(math,currentx,currenty+1,destx,desty)+
               calcPath(math,currentx,currenty-1,destx,desty);
}

Answer 1

传递一组已访问过的单元格。最好的方法是创建一个类，封装单元格中的 x 和 y，并实现比较坐标的 equals() 方法。但是，您可以通过为这两个值创建一个唯一的值来“破解”它。

黑客版本看起来像:

public static int calcPath(int [][] a, int currentx, int currenty, int destx, int desty, Set<Integer> visited) {
    int key = 1000 * currentx + currenty; // unique for x, y
    if (visited.contais(key))
        return 0;
    if (currentx == destx && currenty == desty)
        return 1;
    if(!bounds(a,currentx,currenty)) // if the cell isnt in the array bounds
        return 0;
    Set<Integer> s = new HashSet<Integer>(visited);
    s.add(key);
    return  calcPath(math,currentx+1,currenty,destx,desty,s) +
         calcPath(math,currentx-1,currenty,destx,desty,s)+
          calcPath(math,currentx,currenty+1,destx,desty,s)+
           calcPath(math,currentx,currenty-1,destx,desty,s);
}

请注意，递归时必须创建一个新集合，这样就不会污染调用者堆。

对于初始调用，传入一个空 Set。