在 C++ 递归错误中找到一条迷宫路径

Question

我正在尝试编写一个函数来寻找穿过迷宫的路径。还有另一个函数从文本文件中读取迷宫。现在，当迷宫为 20 行和 20 列时，我编写的用于查找路径的函数可以正常工作，但它不适用于任何其他变体。这是我为该函数编写的代码：

void find_paths(maze m, int r, int c, int rows, int cols) {
  if (r == rows - 1)
    display(m, rows, cols);
  else {
    if (r > 0 && m[r - 1][c] == space) // UP
    {
      m[r - 1][c] = path;
      find_paths(m, r - 1, c, rows, cols);
      m[r - 1][c] = space;
    }
    if (m[r + 1][c] == space) // DOWN
    {
      m[r + 1][c] = path;
      find_paths(m, r + 1, c, rows, cols);
      m[r + 1][c] = space;
    }
    if (m[r][c - 1] == space) // LEFT
    {
      m[r][c - 1] = path;
      find_paths(m, r, c - 1, rows, cols);
      m[r][c - 1] = space;
    }
    if (m[r][c + 1] == space) // RIGHT
    {
      m[r][c + 1] = path;
      find_paths(m, r, c + 1, rows, cols);
      m[r][c + 1] = space;
    }
  }
}

space 是一个 char =' ' 路径是一个 char ='.'

这是程序读取的迷宫文件的屏幕截图。

这是程序执行的屏幕截图。

我是 C++ 的新手，希望你能帮助我。

Answer 1

正如 Benjamin Barrois 在评论中提到的那样，您需要一种方法来了解您是否检查过一条路线，如果是，则不要再次使用。

我建议使用“.”以外的其他字符。（路径）以区分死胡同和实际解决方案，尽管这还不够。

所以我会添加一个名为 visited = 'x'; 的变量并将其用于 return。

此外，您在第一个测试 (UP) 中检查了 r > 0，但在另一个 if()（DOWN、LEFT、RIGHT）中没有检查任何此类限制。虽然如果你在那里有正确的字符，它会起作用（即它会先撞到墙上）但如果不是这样，你就会开始碰到错误的字符。

void find_paths(maze m, int r, int c, int rows, int cols) {
  if (r == rows - 1)
    display(m, rows, cols);
  else {
    if (r > 0 && m[r - 1][c] == space) // UP
    {
      m[r - 1][c] = path;
      find_paths(m, r - 1, c, rows, cols);
      m[r - 1][c] = visited;
    }
    if (r + 1 < rows && m[r + 1][c] == space) // DOWN
    {
      m[r + 1][c] = path;
      find_paths(m, r + 1, c, rows, cols);
      m[r + 1][c] = visited;
    }
    if (c > 0 && m[r][c - 1] == space) // LEFT
    {
      m[r][c - 1] = path;
      find_paths(m, r, c - 1, rows, cols);
      m[r][c - 1] = visited;
    }
    if (c + 1 < cols && m[r][c + 1] == space) // RIGHT
    {
      m[r][c + 1] = path;
      find_paths(m, r, c + 1, rows, cols);
      m[r][c + 1] = visited;
    }
  }
}

也就是说，您当前的算法不会在找到解决方案时停止，因为它是递归的，它将永远继续下去。如果您希望能够摆脱困境，您的函数需要 return true（成功！）或 false（继续搜索）。

虽然使用递归机制的想法对于找到所有解决方案很有用，尤其是（如果你要计算的话）解决方案的长度，所以你 return 只有较短的解决方案（这是通常是关于迷宫搜索的内容。）

bool find_paths(maze m, int r, int c, int rows, int cols) {
  if (r == rows - 1) {
    display(m, rows, cols);
    return true;
  }
  else {
    if (r > 0 && m[r - 1][c] == space) // UP
    {
      m[r - 1][c] = path;
      if(find_paths(m, r - 1, c, rows, cols)) {
        return true;
      }
      m[r - 1][c] = visited;
    }
    if (r + 1 < rows && m[r + 1][c] == space) // DOWN
    {
      m[r + 1][c] = path;
      if(find_paths(m, r + 1, c, rows, cols) {
        return true;
      }
      m[r + 1][c] = visited;
    }
    if (c > 0 && m[r][c - 1] == space) // LEFT
    {
      m[r][c - 1] = path;
      if(find_paths(m, r, c - 1, rows, cols) {
        return true;
      }
      m[r][c - 1] = visited;
    }
    if (c + 1 < cols && m[r][c + 1] == space) // RIGHT
    {
      m[r][c + 1] = path;
      if(find_paths(m, r, c + 1, rows, cols) {
        return true;
      }
      m[r][c + 1] = visited;
    }
  }
  return false;
}

附带说明一下，这并非特定于 C++。

Answer 2

没有太大的错误（尽管可以更有效地完成）。它很可能不起作用，因为您缺少列的边界检查。由于您允许列获取任何值，因此您可能会超出迷宫的范围。您的另一个问题是，当您找到解决方案时，您仍然采用所有其他递归路径。

这只是对您的代码的一个小改动，应该可以工作：

bool done = false;

void find_paths(maze m, int r, int c, int rows, int cols) {
  if(done) {
      return;
  }
  if (r == rows - 1) {
    display(m, rows, cols);
    done = true;
  } else {
    if (r > 0 && m[r - 1][c] == space) // UP
    {
      m[r - 1][c] = path;
      find_paths(m, r - 1, c, rows, cols);
      m[r - 1][c] = space;
    }
    if (m[r + 1][c] == space) // DOWN
    {
      m[r + 1][c] = path;
      find_paths(m, r + 1, c, rows, cols);
      m[r + 1][c] = space;
    }
    if (c > 0 && m[r][c - 1] == space) // LEFT
    {
      m[r][c - 1] = path;
      find_paths(m, r, c - 1, rows, cols);
      m[r][c - 1] = space;
    }
    if (c < cols && m[r][c + 1] == space) // RIGHT
    {
      m[r][c + 1] = path;
      find_paths(m, r, c + 1, rows, cols);
      m[r][c + 1] = space;
    }
  }
}

在 C++ 递归错误中找到一条迷宫路径

Find a path through a maze in C++ recursion error

c++

recursion

maze