迷宫中老鼠的C程序 - 回溯法-2- 技术经验 -卓越飞翔博客

迷宫中的老鼠也是利用回溯的一个常见问题。 I

迷宫是一个二维矩阵，其中一些细胞被阻挡。其中一个单元格是源单元格，我们必须从这里开始。其中另一个是目的地，我们必须到达的地方。我们必须找到一条从源到目的地的路径，而不需要进入任何被封锁的单元格。下面显示了未解决的迷宫的图片。

迷宫中老鼠的C程序 - 回溯法-2

这就是它的解决方案。

迷宫中老鼠的C程序 - 回溯法-2

为了解决这个难题，我们首先从源单元开始，朝路径不被阻挡的方向移动。如果所采取的路径使我们到达目的地，那么难题就解决了。否则，我们会回来改变我们所走的道路的方向。我们也将在代码中实现相同的逻辑。

Input:
maze[][] = {
{0,1,0,1,1},
{0,0,0,0,0},
{1,0,1,0,1},
{0,0,1,0,0},
{1,0,0,1,0}}

Output:
1 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1

解释

首先，我们将制作一个矩阵来表示迷宫，矩阵的元素将是0或1。1表示阻塞的单元格，0表示我们可以移动的单元格。上面显示的迷宫的矩阵如下：

现在，我们将再制作一个相同维度的矩阵来存储解。它的元素也将为 0 或 1。1 将代表我们路径中的单元格，其余单元格将为 0。代表解决方案的矩阵为：

因此，我们现在有了我们的矩阵。接下来，我们将找到从起始单元格到目标单元格的路径，我们将采取的步骤如下：

检查当前单元格，如果它是目标单元格，则拼图已解决。
如果不是，则尝试向下移动并查看是否可以移动到下一个单元格（要移动到一个单元格，它必须是空的且不在路径中）。
如果可以移动到下一个单元格，则继续沿着路径移动到下一个下方单元格。
如果不能，则尝试向右移动。如果右侧被阻塞或已占用，则向上移动。
同样，如果向上移动不可能，我们将简单地移动到左侧单元格。
如果四个方向（向下，向右，向上或向左）都无法移动，则简单地返回并更改当前路径（回溯）。

因此，总结一下，我们尝试从当前单元格移动到其他单元格（向下，向右，向上和向左），如果没有移动可能，则返回并将路径的方向更改为另一个单元格。

printsolution → 此函数只是打印解决方案矩阵。

solvemaze → 这是实际实现回溯算法的函数。首先，我们检查我们的单元格是否是目标单元格，如果是（r==SIZE-1）和（c==SIZE-1）。如果是目标单元格，则我们的拼图已经解决。如果不是，则我们检查它是否是一个有效的移动单元格。有效的单元格必须在矩阵中，即索引必须在0到SIZE-1之间，r>=0 && c>=0 && r

示例

#include <iostream>
using namespace std;
#define SIZE 5
//the maze problem
int maze[SIZE][SIZE] = {
   {0,1,0,1,1},
   {0,0,0,0,0},
   {1,0,1,0,1},
   {0,0,1,0,0},
   {1,0,0,1,0}
};
//matrix to store the solution
int solution[SIZE][SIZE];
//function to print the solution matrix
void printsolution() {
   int i,j;
   for(i=0;i<SIZE;i++) {
      for(j=0;j<SIZE;j++) {
         printf("%dt",solution[i][j]);
      }
      printf("<p></p><p>");
   }
}
//function to solve the maze
//using backtracking
int solvemaze(int r, int c) {
   //if destination is reached, maze is solved
   //destination is the last cell(maze[SIZE-1][SIZE-1])
   if((r==SIZE-1) && (c==SIZE-1) {
      solution[r][c] = 1;
      return 1;
   }
   //checking if we can visit in this cell or not
   //the indices of the cell must be in (0,SIZE-1)
   //and solution[r][c] == 0 is making sure that the cell is not already visited
   //maze[r][c] == 0 is making sure that the cell is not blocked
   if(r>=0 && c>=0 && r<SIZE && c<SIZE && solution[r][c] == 0 && maze[r][c] == 0){
      //if safe to visit then visit the cell
      solution[r][c] = 1;
      //going down
      if(solvemaze(r+1, c))
         return 1;
      //going right
      if(solvemaze(r, c+1))
         return 1;
      //going up
      if(solvemaze(r-1, c))
         return 1;
      //going left
      if(solvemaze(r, c-1))
         return 1;
      //backtracking
      solution[r][c] = 0;
      return 0;
   }
   return 0;
}
int main() {
   //making all elements of the solution matrix 0
   int i,j;
   for(i=0; i<SIZE; i++) {
      for(j=0; j<SIZE; j++) {
         solution[i][j] = 0;
      }
   }
   if (solvemaze(0,0))
      printsolution();
   else
      printf("No solution</p><p>");
   return 0;
}</p>

解释

示例

相关推荐