0

我在使用递归 Java 程序时遇到了问题，目前的问题是我不明白为什么 base case1 if 正在执行。在对 findPath 的初始方法调用中，传递了值 2 和 0。exitRow = 4 和 cols-1 = 11。所以，我的理解是这个基本情况不应该首先进入 if 语句，因为 maze[][] 中的两个位置不一样（maze[4][11] ！ =迷宫[2][0]）。但这正是它正在做的事情。我显然在对 if 结构的理解中遗漏了一些东西，或者我在其他地方有错误，希望能得到一些帮助。

注意：我也试过

if (row == exitRow && col == cols-1)

但这最终给了我一个堆栈溢出。从我对此知之甚少的情况来看，这意味着要么我的递归没有让我更接近基本案例，要么基本案例由于其编写方式而无法访问。根据我一直在使用的本指南http://www.cs.bu.edu/teaching/alg/maze/ ，我假设我的递归是正确的。这使我相信基本情况是问题所在。

非常感谢。

private Boolean findPath(int row, int col)
{
    //base case 1
    if (maze[exitRow][cols-1]==maze[row][col])
    {
        System.out.println("test");//for debugging
        return true;
    }
    //base case 2
    if (maze[row][col] == '#')
    {
        return false;
    }

        maze[row][col] = 'O';
        System.out.println("test1");//for debugging
        steps++;

        //check north
        if (findPath(row+1,col)==true )
        {
        return true;
        }
        //check east
        if (findPath(row,col+1)==true  )
        {
            System.out.println("test2");
        return true;
        }    
        //check south
         if (findPath(row-1,col)== true)
        {
        return true;
        } 
        //check west 
        if (findPath(row,col-1)== true)
        {
        return true;
        }

        System.out.println(steps);
        maze[row][col] = '.';//unmark location

    return false;
}
4

1 回答 1

0 
if( maze[exitRow][cols-1]==maze[row][col] )

如果当前 tile 与退出 tile 的类型相同，则返回 true。由于起点和出口都是楼层（.），因此函数立即返回。坚持这一点：

if (row == exitRow && col == cols-1)

看看你有没有找到出口才是正确的测试。现在溢出：

您将输入的瓷砖标记为O，但如果标记存在，则从不测试该标记，因此您走北-南-北（此时您备注）-南...。由于您已经测试了墙壁 ( if (maze[row][col] == '#'))，因此请测试任一

  • 除了无标记的地板：if (maze[row][col] != '.')
  • 墙壁或标记：if (maze[row][col] == '#' || maze[row][col] == 'O')

请注意，您可以对这两种情况进行相同的处理，因为效果是相同的——不要去那里。

于 2012-11-15T05:47:11.283 回答