数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学迷宫中老鼠问题 - 回溯法-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 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 → 这是我们实现回溯算法的实际函数。首先，我们检查我们的单元格是否是目标单元格 if (r==SIZE-1) and (c==SIZE-1)。如果它是目标单元格，则我们的难题已经解决。如果不是，我们将检查它是否是有效的移动单元格。有效的单元格必须在矩阵中，即索引必须在0到SIZE-1之间 r>=0 && c>=0 && r<SIZE；不得被阻塞 maze[r][c] == 0，并且不得在路径 solution[r][c] == 0 中。如果这是一个有效的移动，那么我们可以自由地进行移动并移动到下一个单元格。首先，我们将尝试下方的单元格 if(solveMaze(r+1, c))。如果它没有给我们解决方案，我们将移动到右边的单元格，同样地移动到上方的和左边的单元格。如果所有单元格都未能给我们解决方案，我们将离开单元格 solution[r][c] = 0 并转到其他单元格。
示例
#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("
");
}
}
//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
");
return 0;
}
3K+ 次浏览
