会员申请：笨宝
1.申请ID：笨宝
2.个人邮箱: 1829913225@qq.com
3.原创技术：走迷宫算法（C回溯递归算法解析）
## 引言
迷宫算法在很多场景都非常实用，比如游戏中的机器人等。而且高级的迷宫算法与回溯、递归也是息息相关的。而且回溯的用途更为广阔，如下棋游戏等。
## 题
请用代码走出下面的迷宫，并且将所有可能都列出。（R为当前开始位置）
```
0 1 2 3 4 5 6 7 8 9
0 # # # # # # # # # #
1 # # # # # #
2 # # # # # # #
3 # # # #
4 # # # # # # #
5 # # # # # #
6 # # # # #
7 # # # # # # # #
8 # #
9 # R # # # # # # #
```
## 原理
方法1：走迷宫算法本质是使用的一个栈，初始化栈为开始顶点（9，1，0）【x:9,y:1,d:0】，在从栈顶取出（x，y，d）【x：表示第几行，y：表示第几列，d：表示从哪个方向走】开始向d方向走之前先进行的判断，如果行的通（不为#，不为R，不越界）进行标记，已表明走过，并且将（x，y，d）放入到栈中；如果行不通则进行方向的加1然后在进行判断，一直到d=4则（就是上下左右都行不通）进行弹栈，依次类推。
方法2：我们从方法1中可以看出迷宫算法一直都是对栈顶进行操作，所以咱们可以不可以用递归来实现一下。思想非常的简单，就是每走一步就向四个方向进行验证，行的通就走，行不通就不走。具体看代码（备注很明白）；
## 代码
```C++
# include "stdio.h"
# include "windows.h"
# define UP 0 //定义上
# define DOWN 1 //定义下
# define LEFT 2 //定义左
# define RIGHT 3 //定义右
# define MAP_MAX 10 //定义最大地图
int map =
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,1,0,1,1,1,1},
{1,0,1,0,1,0,1,1,1,1},
{1,0,1,0,0,0,0,0,1,1},
{1,0,1,0,1,1,0,1,1,1},
{1,0,1,0,0,1,0,1,1,1},
{1,0,1,1,0,1,0,0,0,1},
{1,0,1,1,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,2,1,1,1,1,1,1,0,1}//手动在出发点标了个2
};
/*
打印地图
*/
void print_map()
{
int i,j;
char emt[]=" #R";
//定义显示的数组
putchar(' ');
for(j=0; j<MAP_MAX; j++)
{
printf(" %d", j);
}
putchar('\n');
for(i=0; i<MAP_MAX; i++)
{
printf("%d ", i);
for(j=0; j<MAP_MAX; j++)
{
printf("%c ", emt]);
}
putchar('\n');
}
}
/*
单纯的移动，并且进行值的改变
*/
void move(int &x, int &y, int d)
{
switch(d)
{
case UP:
x--;
break;
case DOWN:
x++;
break;
case LEFT:
y--;
break;
case RIGHT:
y++;
break;
}
}
/*
检查下一步是否可行
x，y点开始
d方向
*/
int inspect(int x,int y,int d)
{
// printf("%d %d %d\n", x,y,d);
move(x,y,d);
if(x<0 || y<0|| x>=MAP_MAX || y>=MAP_MAX || map!=0)
{
return 0;
}
return 1;
}
void print_pro(int s, int e, int n){
/*打印过程*/
Sleep(0);
//system("cls");
printf("当前:(%d, %d) 终点:(%d, %d) 步数:%d\n", s,s,e,e,n);
print_map();
/*--------*/
}
/*
走迷宫（递归回溯所有可能都走）
s是开始坐标
e是结束坐标
n当前第几步
*/
int mazes(int s,int e,int n)
{
if(s==e && s==e){
print_pro(s,e,n);
}
int i;
for(i=0; i<4; i++)//向四个方向同时走
{
if(inspect(s,s,i))//检查i方向是否可以行得通
{
int tx = s, ty = s;//设置临时变量，防止数据混乱
move(tx,ty,i);//向i方向移动一步
map = 2;//标记已走
int ta = {tx,ty};//传值变量
mazes(ta,e,n+1);
map = 0;//取消标记
}
}
}
int main()
{
int n = 0;//初始步数
int s = {9,1};//s初始位置
int e = {9,8};//e终止位置
mazes(s,e,n);//调用走迷宫
putchar('\n');
return 0;
}
```
## 结果
```
当前:(9, 8) 终点:(9, 8) 步数:23
0 1 2 3 4 5 6 7 8 9
0 # # # # # # # # # #
1 # R R R # # # # #
2 # R # R # # # # #
3 # R # R R R R # #
4 # R # # # R # # #
5 # R # # R # # #
6 # R # # # R R R #
7 # R # # # # # # R #
8 # R R #
9 # R # # # # # # R #
当前:(9, 8) 终点:(9, 8) 步数:9
0 1 2 3 4 5 6 7 8 9
0 # # # # # # # # # #
1 # # # # # #
2 # # # # # # #
3 # # # #
4 # # # # # # #
5 # # # # # #
6 # # # # #
7 # # # # # # # #
8 # R R R R R R R R #
9 # R # # # # # # R #
```
## 结语
迷宫算法还是很有研究的必要，因为他涉及 栈、递归、回溯、生成树这些知识点。通过迷宫算法可以更深一步理解。如果有什么问题可以评论，如果想要栈的走迷宫代码，可以私信我。
抱歉，未能达到申请要求，申请不通过，可以关注论坛官方微信（吾爱破解论坛），等待开放注册通知。
页:
[1]