DFS处理迷宫and记录路径（难度：***）
题目：迷宫（蓝桥杯省赛真题） 方法：dfs or bfs 题目链接：第14届蓝桥杯 C&C++ 组省赛夺奖班【第三期】 - 【课后练习】迷宫 - 蓝桥云课 (l**********
掌握本题dfs的思想，我相信你可以做出绝大多数的dfs类型的题！！！
dfs思路：首先遇到迷宫问题，自然而然首选dfs，搭建出模板，确定方向数组（一维或者二维都可），dfs里写两个板块，第一个就是到达终点结束遍历，第二个就是for循环依次dfs到达该点的上下左右四个位置。遇到迷宫可以想到需要检验每一个遍历点的合法性，以这道迷宫题为例可以想到要么x和y的坐标脱离了迷宫盘面，要么撞墙，这就是judge数组的由来。本题需要记录路径，而dfs会遍历所有有可能的路径，通过一个a数组进行记录更新，又因为题目要求使路径尽可能的短，所以我们可以通过这个条件确认优化dfs的方案：剪纸的思想，也就是在基础dfs只含x，y两个基础函数形参的基础上加上第三个参量pos记录路径的长度，引入一个初值无穷大的best变量记录每一次到达终点路径的最小值，举个例子，《例如一次完整的递归使其到达了终点，这时确定了一个best的值，而回溯去遍历其他方案时发现该路径的长度已经大于best的值的时候，就可以直接结束递归，这里就用到了剪纸的思想，可以减少递归的次数，优化了dfs。》
注意点：
1.这里使用一个二维数组来更新记录递归到每一个点的此时的路径长度，这样可以保证回溯的时候记录的信息保留下来
2.这里每一次记录路径为上一个步所走的路径并非目前所走的路径，这就是主函数dfs第三个参数为1的原因，又因为主函数第三个参数并不是0所以路径长度也不是从0开始计的，而是从1开始计的，所以最后的最优解就为best-1。
#include<bits/stdc++.h>
using namespace std;
const int dirx[4]={0,0,1,-1};
const int diry[4]={1,-1,0,0};
const char dir[5]={'R','L','D','U'};
int maze[31][51]=
{
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,1,0,1,0,1,0,1,0,0,1,0,1,1,0,0,1,0,0,1,0,1,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0,
0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,1,0,0,1,1,0,1,0,0,1,0,1,
0,0,1,1,1,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,0,0,0,1,1,0,1,0,0,1,0,1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,
0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,1,0,1,1,
0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,
0,1,1,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,1,1,0,1,0,0,1,1,0,1,0,1,0,1,0,1,1,1,1,0,1,1,1,
0,0,0,0,1,1,0,1,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,1,1,0,0,0,0,0,0,0,
0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,0,1,1,0,0,0,0,1,0,0,0,0,1,1,1,0,1,0,
0,0,0,1,1,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,0,0,1,
0,1,1,0,0,0,1,1,0,1,0,0,0,0,1,1,1,0,0,1,0,0,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,1,0,1,0,0,0,
0,0,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,0,1,0,1,0,1,1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,1,0,1,
0,1,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0,
0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,1,1,1,1,0,1,0,0,0,1,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,1,
0,1,0,1,0,1,0,1,0,0,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,1,1,1,0,1,1,0,1,0,0,0,0,1,0,0,0,
0,1,0,1,0,1,0,1,0,1,0,0,0,0,1,1,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,0,0,1,
0,1,0,0,0,0,0,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,1,0,0,0,0,0,0,0,0,1,0,0,
0,1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1,1,1,0,1,0,1,0,0,1,
0,0,0,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,1,0,1,1,0,1,1,1,0,0,0,0,1,1,0,1,0,1,
0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,1,0,
0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1,
0,1,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,1,1,1,0,1,1,0,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0,1,
0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,1,0,1,0,1,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,
0,1,0,1,0,0,0,0,1,0,0,0,1,1,0,0,1,0,0,0,1,0,0,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,0,1,0,
0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,
0,1,1,0,1,0,0,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1,0,0,1,0,1,1,0,1,1,1,0,1,0,0,0,
0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,1,1,0,0,1,1,
0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,1,0,0,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,
0,1,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,1,0,0,0,1,0,1,1,1,0,1,0,0,0,
0,0,0,1,1,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,1,
0,1,0,0,0,0,0,0,1,1,0,0,1,1,1,0,1,0,1,1,1,0,1,0,0,0,1,0,0,0,1,1,0,1,1,1,0,1,0,1,0,1,1,0,1,1,1,1,0,0,0,
};
int mins[60][60];
char a[2000];
int best;
string ans;
bool judge(int x,int y) {//判断这个点是否越界，是否可以走。
if(x>0&&x<=30&&y>0&&y<=50&&!maze[x][y])
return true;//这个点没越界，而且可以走。
return false;
}
void dfs(int x,int y,int pos) {
if(pos>best)//如果当前路径已经走的步长pos大于之前可行方案最短路径长度 ，
return ;//就无需沿着现有的路径继续走下去了，这个剪枝可以加快速度
if(x==30&&y==50) {//到达终点
string temp;
for(int i=1;i<pos;i++)
temp+=a[i];//路径
if(pos<best) {//更短的路径记录下来
ans=temp;
best=pos;
}
else if(pos==best&&temp<ans) ans=temp;//在实现路时最短的同时，保证字典序最小。
return ;
}
for(int i=0;i<4;i++) {//四个方向
int tox=x+dirx[i];//走向（tox，toy）位置
int toy=y+diry[i];
if(judge(tox,toy)&&pos+1<=mins[tox][toy]) {
//去往（tox，toy) 是合法的，没有越界，也是标记为0的可以行位置
//并且当前的走法能够使得去到 (tox，toy) 步数更小
//就进入此if之内
maze[tox][toy]=1;//现在走到（tox，toy）了，走过了，就标记为障碍，那么下次就不能走了
mins[tox][toy]=pos+1;//当前的走法，到达（tox,toy）的步数 比以前到过的步数更小
//就把当前走法到达 （tox,toy）的步数更新
a[pos]=dir[i];//记录第pos步的方位
dfs(tox,toy,pos+1);//继续以(tox,toy,pos+1)深搜
maze[tox][toy]=0;//回溯找短的路，或者是字典序最小的。
//恢复 （tox，toy）为0，即可行状态，好尝试其他位置在以后会走向它
}
}
}
int main()
{
memset(mins,1,sizeof(mins));
best=1<<28;
maze[1][1]=1;//标记起始点走过来，也就是变为障碍物，不再能走到它
dfs(1,1,1);//从起始点（1，1）1步 开始深搜
cout<<ans<<endl;
cout<<best-1<<endl;
return 0;
}
#include <iostream>
#include <queue>
using namespace std;
//#define maxn 10005 超内存
#define maxn 50
const int row =30,col =50;
int step=0;
string maze[30]= {
"01010101001011001001010110010110100100001000101010",
"00001000100000101010010000100000001001100110100101",
"01111011010010001000001101001011100011000000010000",
"01000000001010100011010000101000001010101011001011",
"00011111000000101000010010100010100000101100000000",
"11001000110101000010101100011010011010101011110111",
"00011011010101001001001010000001000101001110000000",
"10100000101000100110101010111110011000010000111010",
"00111000001010100001100010000001000101001100001001",
"11000110100001110010001001010101010101010001101000",
"00010000100100000101001010101110100010101010000101",
"11100100101001001000010000010101010100100100010100",
"00000010000000101011001111010001100000101010100011",
"10101010011100001000011000010110011110110100001000",
"10101010100001101010100101000010100000111011101001",
"10000000101100010000101100101101001011100000000100",
"10101001000000010100100001000100000100011110101001",
"00101001010101101001010100011010101101110000110101",
"11001010000100001100000010100101000001000111000010",
"00001000110000110101101000000100101001001000011101",
"10100101000101000000001110110010110101101010100001",
"00101000010000110101010000100010001001000100010101",
"10100001000110010001000010101001010101011111010010",
"00000100101000000110010100101001000001000000000010",
"11010000001001110111001001000011101001011011101000",
"00000110100010001000100000001000011101000000110011",
"10101000101000100010001111100010101001010000001000",
"10000010100101001010110000000100101010001011101000",
"00111100001000010000000110111000000001000000001011",
"10000001100111010111010001000110111010101101111000"};
bool vis[maxn][maxn];//标记
int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}};//D L R U
bool judge(int x,int y) {//判断这个点是否越界，是否可以走。
if(x>=0&&x<row&&y>=0&&y<col&&maze[x][y]!='1')
return true;//这个点没越界，而且可以走。
return false;
}
struct node
{
int x,y,step;//某个位置的x、y坐标值，
//按照某种路径从起到走到此处的步数为step
char direction;//存储D L R U，由何种走向到达此处的
};
node father[maxn][maxn];//当前节点的父节点
node now,nextpos;//指向当前和下一个位置
void dfs(int x,int y)//递归打印
{
if(x==0&&y==0)//找到起点开始正向打印路径
return;//直至搜到（0，0)位置而终止
else
dfs(father[x][y].x,father[x][y].y);
//因为father（x，y）存储了它上一个位置在哪里，那么就可以顺藤摸瓜
//而找出再上一个位置，如此搜索下去。
cout<<father[x][y].direction;//打印出所记录的 direction方位
//逐层返回，就从（0，0）开始，逐层打印出 direction方位
}
void bfs(int x,int y)
{
queue<node> q;
now.x=x;
now.y=y;
now.step=0;
q.push(now);
father[x][y].x=10000;
father[x][y].y=10000;
father[x][y].direction=0;
vis[x][y]=true;
while(!q.empty())
{//队列空就不做了，能达到的位置全都宽搜达到
now=q.front();//获得队首元素 ，作为当前位置点
q.pop();//队首元素出队列
for(int i=0;i<4;i++)//走“下左右上”按字典序的四个方向
{
int tox=now.x+dir[i][0];//现在的位置now加偏移量后,
int toy=now.y+dir[i][1];//得到下一个位置的坐标 (tox,toy)
//if(in(tox,toy)&&!vis[tox][toy]&&maze[tox][toy]!='1')
if(judge(tox,toy)&& !vis[tox][toy])
{//满足条件“在合法范围内in返回真，vis是0没有用过，不是障碍1”
vis[tox][toy]=true;//现在标记(tox,toy)位置为用过
nextpos.x=tox;//下面就走向这个位置，记录在next中
nextpos.y=toy;
nextpos.step=now.step+1;//到达next位置的步数 是now的步数加1
q.push(nextpos);//压入队列，把nextpos整个点的信息放入队列
father[tox][toy].x=now.x;//存储父节点坐标
father[tox][toy].y=now.y;//(tox,toy)来自于（now.x,now.y)
if(i==0)// (tox,toy)是从什么方向而来的
father[tox][toy].direction='D';
else if(i==1)
father[tox][toy].direction='L';
else if(i==2)
father[tox][toy].direction='R';
else if(i==3)
father[tox][toy].direction='U';
//father(tox,toy)的 x、y、direction表明了
//走到(tox,toy)这个点，是从其（x,y)点往direction方向而来的。
//换句话说，就是存储了它的上一个点的位置，及何方位而来。
}
}
}
}
int main()
{
bfs(0,0);//从左上角（0，0)位置开始宽搜
dfs(29,49);//打印路径 ，为到达右下角（29，49）而深搜打印路径
//因为father（29，49）存储了它上一个位置在哪里，那么就可以顺藤摸瓜
//而找出再上一个位置，如此搜索下去，直至搜到（0，0)位置而终止，
//返回上一层打印出所记录的 direction方位，逐层返回，就把从（0，0）走到
//(29,49)所途径所有点时的 direction都打印出来了。
//问题：如何达到字典序？
//回答：因为在BFS时 已经按照DLRU顺序了
return 0;
}
查看29道真题和解析
投递荣耀终端等公司7个岗位 >
拼多多HR面75人在聊