java - 编写 "Rat in a maze"问题的递归解决方案很困难

Question

我的问题本质上是对递归的怀疑。我正在解决经典的“迷宫中的老鼠”DFS 遍历问题。我的输入是一个 n*n int 数组 a[][]，其中索引 i 和 j，a[i][j] 可以是 0 或 1。 0 表示假设的老鼠无法访问该元素，1 表示可以。老鼠只能向下("D")或向右("R")移动。任务是输出所有运动字符串，例如代表老鼠穿过迷宫的运动的 RDRDRD。老鼠从a[0][0]出发，必须到达a[n-1][n-1]。输入是迷宫本身。

我写了下面的代码

 public boolean isSafe(int x, int y, int[][] a, int n)
 {
    if(x >= 0 && x < n && y >= 0 && y < n && a[x][y] == 1)
        return true;
    else
        return false;
 }
 public ArrayList<String> printPath(int[][] a, int n)
 {
     ArrayList<String> res = new ArrayList<String>();
     solve(0,0,new String(), res,a,n);
     return res;
 }
 public void solve(int x, int y, String sol, ArrayList<String> res , 
 int[][]a, int n)
 {
     if(x == n-1 && y == n-1)
     {
         res.add(sol);
         return;
     }
     y++;
     if(isSafe(x,y,a,n))
     {
         solve(x,y,sol + "R",res,a,n);
     }
     else 
         y--;
     x++;
     if(isSafe(x,y,a,n))
     {
         solve(x,y,sol+"D",res,a,n);
     }
     else
         x--;
 }`

其中 isSafe 检查是否允许移动，printPath 是用于打印输出的辅助函数，solve 是用于打印输出的递归函数遍历迷宫。a 将迷宫数组表示为二维数组。对于输入

{1 0 0 0 
 1 1 0 1 
 0 1 0 0 
 0 1 1 1}

我得到以下输出

DRDDRR DDDRR

显然第二个字符串代表了错误的结果。

但是，当我像这样更改 solve 函数时

public void solve(int x, int y, String sol, ArrayList<String> res, 
int[][]a, int n)
 {
    if(x == n-1 && y == n-1)
    {
        res.add(sol);
        return;
    }
    if(!isSafe(x,y,a,n))
       return;
    solve(x+1,y,sol + "D",res,a,n);
    solve(x,y+1,sol + "R",res,a,n);    
    return;  
 }

我得到了正确的输出。我无法理解的是导致我之前的解决方案输出不正确的原因，因为对我来说这两个解决方案在逻辑上是相似的。我知道这是一篇很长的文章，但任何见解都将不胜感激。

Answer 1

在第一个解决方案中，只有当使用增量值调用 isSafe 返回负值并转入检查 时，变量增量 y++ 才会被撤消。 >x 如果这是真的。这意味着对右侧具有有效邻居的字段(特别是字段 [1][0])的向下检查将使用 y 的递增值而不是正确的值执行.

如果你像这样修改第一个解决方案

y++;
if(isSafe(x,y,a,n)){
    solve(x,y,sol + "R",res,a,n);
}
y--;

第一个解决方案将与第二个解决方案一样正常工作。在第二个解决方案中，增量仅在函数参数上完成，而不是在局部变量上完成。