题目：

既然是迷宫问题的探讨建议先看看这个文章

关于多种运用bfs的最短路径问题：

1.开锁问题
2.多源bfs问题

两种形式的 单向bfs模板(其实双向bfs也差不多就这两种)

第一种

这一种形式完全不会将重复的子问题入队，也就是每层都会是不一样的遍历结果出现，这一种形式虽然很严谨，但是有些时候比如开锁问题的时候有death密码则会出现代码的赘余，但是在需要用到子问题路径的题目中你只能选择这种扩散子问题时必不会重复的单向bfs。

模板

void bfs(vector<int>grid){//visit防止走回头路set<...>visit;queue<..>start;start.push(...);visit.insert(start.front());//用于每层遍历完后就+1int step = 0;while(!start.empty()){int size = start.size();for(int i=0;i<size;i++){auto t = start.front();start.pop();//如果此时走到了尽头(终点)故最短路径找到。if(t==end){cout<<step;return;}//开始扩散子选择for(...){if(!visit.count(subQ)&&...){start.push(subQ);visit.insert(subQ);...}}//每遍历完一层步数就+1step++;}
}
}

第二种

第二种形式，虽在每层遍历时不会出现回头路操作(毕竟都continue了)，但是入到队列的扩散元素是会有重复元素的，所以每个子问题的路径到达方式如果在扩散时更新，肯定是会出错的，毕竟会有重复的选择，故路径会不对劲，但是不影响最终的扩散结果，毕竟有continue，这种模板适用于钥匙开锁问题，可将death密码和visit密码用一个visit存储，即该问题不会问中途的路径，而只问最终的结果step的问题，这种写法会更方便。

模板

void bfs(vector<int>grid){//visit防止走回头路set<...>visit;queue<..>start;start.push(...);//用于每层遍历完后就+1int step = 0;while(!start.empty()){int size = start.size();for(int i=0;i<size;i++){auto t = start.front();start.pop();//如果此时走到了尽头(终点)故最短路径找到。if(t==end){cout<<step;return;}//在这里进行回头路判断与添加//这样子问题仍然可能会选择正在遍历的该层元素，但是没关系，下次遍历会被continue，只是这样无法对正确的路径进行判断if(visit.count(t))continue;visit.insert(t);//开始扩散子选择for(...){if(!visit.count(subQ)&&...){start.push(subQ);...}}//每遍历完一层步数就+1step++;}
}
}

解题思路

很明显根据题目的描述，明显只能选择第二种单向bfs来实现。
这个难点就在于中途的路径选择需要你打印出来，
这个可以用两种方法(我目前所知道的)

1. 用一个单独的表来记录每个所到的格子我们所采取的操作(一定要对应一个数字用于反向跳回)
2. 直接用一个结构体其中包含string，用于表示每个格子状态的所采用的操作，当某个格子成功到达终点打印它的string即可。

解法一代码：

#include <bits/stdc++.h>
#define N 500
using namespace std;
//由于需要详细的字符路径所以只能用单向bfs+用额外的表存在对应位置的移动方式const int dirc[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
const char h[4] = {'U','D','L','R'};
//该表用于存储移动到对应位置所用的操作(不能直接存字符UDLR，这样无法找寻上一次的位置)
//想要打印相应位置采取的操作的字符可以直接通过存储的数字0、1、2、3得到对应的字符，
//同样也可以通过该数字获取dirc数组从而跳转到上一格
int listT[N][N];
set<pair<int,int> >visit;
void bfs(vector<string>&grid){int n = grid.size();int m = grid[0].size();queue<pair<int,int> >start;int step = 0;//从左上角开始遍历start.push({0,0});while(!start.empty()){int size = start.size();for(int i = 0;i<size;i++){pair<int,int>t = start.front();start.pop();if(t==make_pair(n-1,m-1)){cout<<step<<endl;return;}//开始扩散int x = t.first;int y = t.second;for (int i = 0; i < 4; i++){int newX = x+dirc[i][0];int newY = y+dirc[i][1];if(newX>=0&&newX<n&&newY>=0&&newY<m&&!visit.count({newX,newY})){if(grid[newX][newY]=='0'){start.push({newX,newY});visit.insert({newX,newY});//用于存储该次步骤在格子对应位置的操作listT[newX][newY] = i;}}}}//更新步数step++;}}
//用dfs的方法反跳回去并打印
void dfs(int x, int y){//当到达起点时，肯定是不需要任何操作的。//用dfs实现后序遍历即可得到答案(从终点一直到起点的后一个，然后再开始打印答案)if(x==0&&y==0)return;//这就是用listT存储对应位置上次操作的作用dfs(x-dirc[listT[x][y]][0],y-dirc[listT[x][y]][1]);cout<<h[listT[x][y]];
}
int main() {int m,n;cin>>n>>m;
vector<string >grid(n);for(int i=0;i<n;i++){cin>>grid[i];}bfs(grid);dfs(n-1,m-1);return 0;
}

解法二代码：

#include <bits/stdc++.h>
using namespace std;
const int dirc[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
char h[4] = {'U','D','L','R'};
set<pair<int,int> >visit;
//构造结构体用于记录每次所扩散到的位置的操作
typedef struct{pair<int,int>pos;string op;
}sub;
void bfs(vector<string>&grid){int n = grid.size();int m = grid[0].size();queue<sub>start;int step = 0;//从左上角开始遍历sub start_0 = {{0,0},""};start.push(start_0);while(!start.empty()){int size = start.size();for(int i = 0;i<size;i++){sub t = start.front();start.pop();if(t.pos==make_pair(n-1,m-1)){cout<<step<<endl;cout<<t.op;return;}//开始扩散int x = t.pos.first;int y = t.pos.second;for (int i = 0; i < 4; i++){int newX = x+dirc[i][0];int newY = y+dirc[i][1];if(newX>=0&&newX<n&&newY>=0&&newY<m&&!visit.count({newX,newY})){if(grid[newX][newY]=='0'){//构造子结构体入队string tt = t.op;tt.push_back(h[i]);sub e = {{newX,newY},tt};start.push(e);visit.insert({newX,newY});}}}}//更新步数step++;}}int main() {int m,n;cin>>n>>m;vector<string >grid(n);for(int i=0;i<n;i++){cin>>grid[i];}bfs(grid);return 0;
}