0

就是想...

void mazeTraversal(char maze[12][12], int x, int y)
{
if (maze[x + 1][y] == '.')
    mazeTraversal(maze, ++x, y);
if (maze[x][y + 1] == '.')
    mazeTraversal(maze, x, ++y);
if (maze[x - 1][y] == '.')
    mazeTraversal(maze, --x, y);
if (maze[x][y - 1] == '.')
    mazeTraversal(maze, x, --y);
   return;
}

当我遇到死胡同时，我应该恢复到调用的前一个实例，而不是直接回到主函数吗？如果我有什么问题，请告诉我。

4

2 回答 2

2

以下地址使用返回值来捕获“正确路径”信息并提供基本情况条件。然而，原始代码的另一个关键问题是使用++/--它会对各个变量产生副作用。出于这个原因，下面的代码避开了这些运算符。

执行此操作的主要方法是返回一个值 - 例如，如果此路径导致并结束，则返回true ，否则返回false。

一个非常原始的转换将如下所示。注意基本情况的添加——这意味着我们可以停止递归。返回 True 以便之前的调用者也知道他们可以停止查找，并且函数堆栈将快速展开回“main”。

bool mazeTraversal(char maze[12][12], int x, int y) {
  // This is the BASE CASE and means WE ARE DONE LOOKING
  if (maze[x][y] == 'X') return true; // found end!

  if (maze[x + 1][y] == '.')
    if (mazeTraversal(maze, x + 1, y)) return true;

  if (maze[x][y + 1] == '.')
     if (mazeTraversal(maze, x, y + 1)) return true;

  if (maze[x - 1][y] == '.')
     if (mazeTraversal(maze, x - 1, y)) return true;

  if (maze[x][y - 1] == '.')
     if (mazeTraversal(maze, x, y - 1)) return true;

  return false; // didn't find any valid path from here
}

请注意，我删除++/--以避免奇怪的副作用。

但是，我们可以做得更好并清理一些代码。关键的区别是每个递归调用检查当前位置- 而不是其邻居的位置。

bool mazeTraversal(char maze[12][12], int x, int y) {
  if (maze[x][y] == 'X')
    return true; // found end!

  if (maze[x][y] == '.') {
    // we are still on a path - see where exploration leads!
    if (mazeTraversal(maze, x + 1, y)) return true;
    if (mazeTraversal(maze, x, y + 1)) return true;
    if (mazeTraversal(maze, x - 1, y)) return true;
    if (mazeTraversal(maze, x, y - 1)) return true;
  }

  // Didn't find any valid path from here -
  // maybe "here" is a wall!
  return false;
}

最终，您可能希望在找到的路径上执行其他操作（即它读取“返回真”的位置），例如记录当前位置。

另请注意，根据语言，这些if (mazeTraversal..) return true东西也可以“清理”。在 C 中，考虑使用短路 ||运算符。然后我们可以将最终情况缩短为：

int leadsToEnd =
       (maze[x][y] == 'X')      // at end
    || (maze[x][y] == '.')      // or not end ..
       && (mazeTraversal(maze, x + 1, y)   // but may lead to end
           || mazeTraversal(maze, x, y + 1)
           || mazeTraversal(maze, x - 1, y) 
           || mazeTraversal(maze, x, y - 1));

因此整个函数有效地变为return leadsToEnd（根据需要替换上述表达式）。当然，你必须决定哪种方法——后一个例子可以说是过于聪明了——或者这种方法的混合对你来说最有意义。

于 2013-09-12T23:32:01.020 回答
0

正如你现在所拥有的，当你遇到死胡同时，你就回来了。这是正确的，因为您将备份到上一个呼叫，然后选择下一个路径。当您遍历所有可能的路径时，您的顶级调用将返回。

于 2013-09-12T23:23:57.750 回答