会员申请：笨宝

1.申请ID：笨宝 2.个人邮箱: [email]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[MAP_MAX][MAP_MAX] =
{
{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[map[i][j]]);
}
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[x][y]!=0)
{
    return 0;
}

return 1;

}

void print_pro(int s[2], int e[2], int n){
/打印过程/
Sleep(0);
//system("cls");
printf("当前:(%d, %d) 终点:(%d, %d) 步数:%d\n", s[0],s[1],e[0],e[1],n);
print_map();
/--------/
}

/
走迷宫（递归回溯所有可能都走）
s是开始坐标
e是结束坐标
n当前第几步
/
int mazes(int s[2],int e[2],int n)
{
if(s[0]==e[0] && s[1]==e[1]){
print_pro(s,e,n);
}

int i;
for(i=0; i<4; i++)//向四个方向同时走
{
    if(inspect(s[0],s[1],i))//检查i方向是否可以行得通
    {
        int tx = s[0], ty = s[1];//设置临时变量，防止数据混乱
        move(tx,ty,i);//向i方向移动一步
        map[tx][ty] = 2;//标记已走
        int ta[2] = {tx,ty};//传值变量
        mazes(ta,e,n+1);
        map[tx][ty] = 0;//取消标记
    }
}

}

int main()
{
int n = 0;//初始步数
int s[2] = {9,1};//s初始位置
int e[2] = {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 #

## 结语

迷宫算法还是很有研究的必要，因为他涉及 栈、递归、回溯、生成树这些知识点。通过迷宫算法可以更深一步理解。如果有什么问题可以评论，如果想要栈的走迷宫代码，可以私信我。

Hmily

抱歉，未能达到申请要求，申请不通过，可以关注论坛官方微信（吾爱破解论坛），等待开放注册通知。