输入： 第一行两个整数n， m，为迷宫的长宽。 接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。
输出： 第一行一个数为需要的最少步数K。 第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。 样例输入： 3 3 001 100 110 样例输出： 4 RDRD
思路：BFS，因为要找字典序最小的最短路，直接按D,L,R,U的顺序遍历即可解决问题;需要开结构体 struct node{ int x,y,step; //x,y表示坐标，step表示步数； string s; //表示从起点到终点移动的字符串; };
代码： //BFS解决学霸的迷宫 #include<bits/stdc++.h> using namespace std; #include const int maxn=999; bool vis[maxn][maxn]; int n,m; char map1[maxn][maxn]; //要求多条最短路中的字典序最小的，直接按D L R U 的顺序遍历 int dx[4]={1,0,0,-1}; int dy[4]={0,-1,1,0}; string mac[]={“D”,“L”,“R”,“U”}; struct node{ int x,y,step; string s; node(int a,int b,int c){ x=a; y=b; step=c; s=""; } }; bool BFS(int x,int y) { vis[x][y]=true; node now=node(x,y,0); queue q; //q是队列 q.push(now); while(!q.empty()) { node k=q.front(); q.pop(); int ux=k.x; int uy=k.y; int up=k.step; string us=k.s; if(uxn&&uym) { cout<<up<<endl<<us; return true; } for(int i=0;i<4;i++) { int newx=ux+dx[i]; int newy=uy+dy[i]; int newp=up+1; if(newx<1||newx>n||newy<1||newy>m||vis[newx][newy]||map1[newx][newy]==‘1’) continue; else{ vis[newx][newy]=true; node newn=node(newx,newy,newp); newn.s=us+mac[i]; q.push(newn); } }
} return false;} int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) cin>>map1[i][j]; } BFS(1,1); return 0;
}
