在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 =''path是一个char ='。'

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

这是程序执行的截图。

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

Answer 1

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

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

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;
    }
  }
}

Answer 2

正如Benjamin Barrois的评论中提到的，你需要一种方法来知道你检查了一条路线，如果是这样的话就不要再拿它了。

我会建议另一个字符而不是'。' （路径）将死端与实际解决方案区分开来，尽管这还不够。

所以我会添加一个名为visited = 'x';的变量并在返回时使用它。

另外，你在第一次测试（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;
    }
  }
}

话虽这么说，你的当前算法在找到解决方案时不会停止，因为它是递归的，它会永远持续下去。如果你想要拯救，你的功能需要返回true（成功！）或false（继续搜索）。

虽然使用递归机制的想法可以用于查找所有解决方案，尤其是（如果您要计算）解决方案的长度，因此您只返回较短的解决方案（这通常是迷宫搜索的内容。）

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 ++特有的。