时间戳

首页 > 解决方案 > 难以编写“迷宫中的老鼠”问题的递归解决方案

java - 难以编写“迷宫中的老鼠”问题的递归解决方案

问题描述

我的问题本质上是对递归的怀疑。我正在解决经典的“迷宫中的老鼠”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;  
 }

我得到正确的输出。我不明白是什么导致了我之前的解决方案中的错误输出，因为对我来说这两个解决方案在逻辑上是相似的。我知道这是一个很长的阅读，但任何见解将不胜感激。

标签： javarecursion

解决方案

在第一个解决方案中，变量增量只有在对增量值y++的调用返回负值时才撤消，isSafe并继续检查x它是否为真。这意味着对右侧具有有效邻居的字段（特别是字段 [1][0]）的向下检查将使用递增的值y而不是正确的值执行。

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

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

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

推荐阅读