迷宫中的老鼠也是利用回溯的一个常见问题。 I
迷宫是一个二维矩阵，其中一些细胞被阻挡。其中一个单元格是源单元格，我们必须从这里开始。其中另一个是目的地，我们必须到达的地方。我们必须找到一条从源到目的地的路径，而不需要进入任何被封锁的单元格。下面显示了未解决的迷宫的图片。
这就是它的解决方案。
为了解决这个难题，我们首先从源单元开始，朝路径不被阻挡的方向移动。如果所采取的路径使我们到达目的地，那么难题就解决了。否则，我们会回来改变我们所走的道路的方向。我们也将在代码中实现相同的逻辑。
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 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0
现在，我们将再制作一个相同维度的矩阵来存储解。它的元素也将为 0 或 1。1 将代表我们路径中的单元格，其余单元格将为 0。代表解决方案的矩阵为：
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
因此，我们现在有了我们的矩阵。接下来，我们将找到从起始单元格到目标单元格的路径，我们将采取的步骤如下：
检查当前单元格，如果它是目标单元格，则拼图已解决。
如果不是，则尝试向下移动并查看是否可以移动到下一个单元格（要移动到一个单元格，它必须是空的且不在路径中）。
如果可以移动到下一个单元格，则继续沿着路径移动到下一个下方单元格。
如果不能，则尝试向右移动。如果右侧被阻塞或已占用，则向上移动。
同样，如果向上移动不可能，我们将简单地移动到左侧单元格。
如果四个方向（向下，向右，向上或向左）都无法移动，则简单地返回并更改当前路径（回溯）。
因此，总结一下，我们尝试从当前单元格移动到其他单元格（向下，向右，向上和向左），如果没有移动可能，则返回并将路径的方向更改为另一个单元格。
printsolution → 此函数只是打印解决方案矩阵。
solvemaze → 这是实际实现回溯算法的函数。首先，我们检查我们的单元格是否是目标单元格，如果是（r==SIZE-1）和（c==SIZE-1）。如果是目标单元格，则我们的拼图已经解决。如果不是，则我们检查它是否是一个有效的移动单元格。有效的单元格必须在矩阵中，即索引必须在0到SIZE-1之间，r>=0 && c>=0 && r 以上是迷宫中老鼠的C程序 - 回溯法-2的详细内容。更多信息请关注PHP中文网其他相关文章！示例
#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("%d\t",solution[i][j]);
}
printf("</p><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;
}登录后复制
