迷宫中的老鼠也是利用回溯的一个常见问题。 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 01 1 1 1 00 0 0 1 00 0 0 1 10 0 0 0 1
解释
首先，我们将制作一个矩阵来表示迷宫，矩阵的元素将是0或1。1表示阻塞的单元格，0表示我们可以移动的单元格。上面显示的迷宫的矩阵如下：
0 1 0 1 10 0 0 0 01 0 1 0 10 0 1 0 01 0 0 1 0
现在，我们将再制作一个相同维度的矩阵来存储解。它的元素也将为 0 或 1。1 将代表我们路径中的单元格，其余单元格将为 0。代表解决方案的矩阵为：
1 0 0 0 01 1 1 1 00 0 0 1 00 0 0 1 10 0 0 0 1
因此，我们现在有了我们的矩阵。接下来，我们将找到从起始单元格到目标单元格的路径，我们将采取的步骤如下：
检查当前单元格，如果它是目标单元格，则拼图已解决。
如果不是，则尝试向下移动并查看是否可以移动到下一个单元格（要移动到一个单元格，它必须是空的且不在路径中）。
如果可以移动到下一个单元格，则继续沿着路径移动到下一个下方单元格。
如果不能，则尝试向右移动。如果右侧被阻塞或已占用，则向上移动。
同样，如果向上移动不可能，我们将简单地移动到左侧单元格。
如果四个方向（向下，向右，向上或向左）都无法移动，则简单地返回并更改当前路径（回溯）。
因此，总结一下，我们尝试从当前单元格移动到其他单元格（向下，向右，向上和向左），如果没有移动可能，则返回并将路径的方向更改为另一个单元格。
printsolution → 此函数只是打印解决方案矩阵。
solvemaze → 这是实际实现回溯算法的函数。首先，我们检查我们的单元格是否是目标单元格，如果是（r==SIZE-1）和（c==SIZE-1）。如果是目标单元格，则我们的拼图已经解决。如果不是，则我们检查它是否是一个有效的移动单元格。有效的单元格必须在矩阵中，即索引必须在0到SIZE-1之间，r>=0 && c>=0 && r
示例
#include using namespace std;#define SIZE 5//the maze problemint 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 solutionint solution[SIZE][SIZE];//function to print the solution matrixvoid printsolution() { int i,j; for(i=0;i<SIZE;i++) { for(j=0;j<SIZE;j++) { printf("%dt",solution[i][j]); } printf(""); }}//function to solve the maze//using backtrackingint 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;}
以上就是迷宫中老鼠的C程序 – 回溯法-2的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444944.html
微信扫一扫 
支付宝扫一扫 
