迷宫问题 （C语言代码）bfs

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=500;
struct node
{
 int x,y,step;
};
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
bool vis[maxn][maxn];
char mat[maxn][maxn];  
int main()
{
 bool flag;
 char ch;
 int sx,sy,t,n,m;
 cin>>t;
 while(t--){
  flag=0;
  struct node top,nex;
  memset(vis,0,sizeof(vis));
  memset(mat,0,sizeof(mat));
  cin>>n>>m;
  for(int i=1;i<=n;i++){
   for(int j=1;j<=m;j++){
    cin>>ch;
    if(ch=='S'){
     sx=i,sy=j;
    }
    mat[i][j]=ch;
   }
  }
  queue<node> q;
  top.x=sx,top.y=sy,top.step=0;
  vis[sx][sy]=1;
  q.push(top);
  while(!q.empty()){
   top=q.front();
   q.pop();
   for(int i=0;i<4;i++){
    nex.x=top.x+dx[i];
    nex.y=top.y+dy[i];
    if(nex.x<1||nex.y<1||nex.x>n||nex.y>m||vis[nex.x][nex.y]||mat[nex.x][nex.y]=='#'){
     continue;
    }
    nex.step=top.step+1;
    if(mat[nex.x][nex.y]=='E'){
     flag=1;
     break;
    } 
    vis[nex.x][nex.y]=1;
    q.push(nex);
   }
   if(flag)
   break;
  }
  if(flag)
  cout<<nex.step<<endl;
  else
  cout<<-1<<endl;
 }
 
 return 0;
}