迷宫问题 （C++代码）

解题思路:
宽度优先搜索的常规题

注意事项:
需要注意判断：如果不存在通路需要返回-1（否则只能过50%，存在一半的数据）；

参考代码:

#include <iostream>

#include <algorithm>

#include <cmath> 

#include <string>

#include <cstring>

#include <map> 

#include <cstdio>

#include <queue>

using namespace std;

const int INF=0x3f3f3f3f;

typedef pair<int,int> P; 

char maze[105][105];

int N,M;

int sx,sy;

int gx,gy;

int d[105][105];

int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};

int t;

int bfs()

{

queue<P> que;

for(int i=0;i<N;i++){

for(int j=0;j<M;j++){

d[i][j]=INF;

}

}

que.push(P(sx,sy));

d[sx][sy]=0;

while(que.size()){

P p=que.front();

que.pop();

if(p.first==gx&&p.second==gy) break;

for(int i=0;i<4;i++){

int nx=p.first+dx[i],ny=p.second+dy[i];

if(nx>=0&&nx<N&&ny>=0&&ny<M&&maze[nx][ny]!='#'&&d[nx][ny]==INF){

que.push(P(nx,ny));

d[nx][ny]=d[p.first][p.second]+1;

}

}

}

if(d[gx][gy]==INF) return -1;

else return d[gx][gy];

}

int main()

{

while(cin>>t){

while(t--){

cin>>N>>M;

for(int i=0;i<N;i++){

for(int j=0;j<M;j++){

cin>>maze[i][j];

if(maze[i][j]=='S'){

sx=i;

sy=j;

}

if(maze[i][j]=='E'){

gx=i;

gy=j;

}

}

}

cout<<bfs()<<endl;

}

}

return 0;

}