蓝桥杯算法提高VIP-学霸的迷宫 （C++代码）

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=500;
int dx[]={1,0,0,-1}; // 下 D 左 L 右 R  上 U
int dy[]={0,-1,1,0};
bool vis[maxn][maxn];
char  mat[maxn][maxn];
string s[maxn],ans;
struct node
{
 int x,y,step;
 string s;
};
int main()
{ 
 int n,m;
 cin>>n>>m;
 memset(mat,'1',sizeof(mat));
 for(int i=1;i<=n;i++){
  for(int j=1;j<=m;j++){
   cin>>mat[i][j];
  }
 }
 node top,next;
 top.x=1;top.y=1;top.step=0,top.s="";
 vis[1][1]=1;
 queue<node> q;
 q.push(top);
 while(!q.empty()){
  top=q.front();
  q.pop();   
  for(int i=0;i<4;i++){
   next.x=top.x+dx[i];
   next.y=top.y+dy[i];
   if(mat[next.x][next.y]=='1'||next.x<1||next.y<1||vis[next.x][next.y]||next.x>n||next.y>m)
    continue;
   if(i==0){
    next.s=top.s+"D";
   }else if(i==1){
    next.s=top.s+"L"; 
   }else if(i==2){
    next.s=top.s+"R";
   }else{
    next.s=top.s+"U"; 
   }
   next.step=top.step+1;  
   if(next.x==n&&next.y==m){
    cout<<next.step <<endl;
    cout<<next.s<<endl;
    return 0;
   }    
   vis[next.x][next.y]=1;
   q.push(next);
  }
 }
 return 0; 
}