【OJ】迷宫最短路径问题（maze）acmclub.com 1102

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int yy,xx,sx,sy,ex,ey,d[101][101]={0};
char c,maze[101][101];
int dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};
struct NODE{
	int nx,ny;
}node1,node2;
void bfs(){
	queue<NODE>q;node1.nx=sx;node1.ny=sy;
	q.push(node1);
	while(q.size()){
		node2=q.front();q.pop();
		if(node2.nx==ex&&node2.ny==ey)break;
		for(int k=0;k<4;k++){
			int x=node2.nx+dx[k],y=node2.ny+dy[k];
			if(x>=1&&x<=xx&&y>=1&&y<=yy&&maze[y][x]!='#'&&d[y][x]==10000){
				node1.nx=x;node1.ny=y;q.push(node1);//maze[y][x]!='#'&&d[y][x]==10000
				d[y][x]=d[node2.ny][node2.nx]+1;
			}
		}
	}
}
int main(){
//	freopen("1.txt","r",stdin);
	int t;cin>>t;
	while(t--){
		cin>>yy>>xx;getchar();
		for(int i=1;i<=yy;i++){
			for(int j=1;j<=xx;j++){
				c=getchar();
				maze[i][j]=c;
				d[i][j]=10000;
				if(c=='E'){ex=j;ey=i;}
				else if(c=='S'){sx=j;sy=i;d[i][j]=0;}				
			}
			getchar();
		}
/*		for( i=1;i<=yy;i++){
			for(int j=1;j<=xx;j++){
			cout<<maze[i][j];}cout<<endl;
		}
*/		bfs();
		if(d[ey][ex]!=10000)
			cout<<d[ey][ex]<<endl;
		else cout<<-1<<endl;//if -1
/*		for( i=1;i<=yy;i++){
			for(int j=1;j<=xx;j++){
			printf("%6d",d[i][j]);}cout<<endl;
		}
*/	}
	return 0;
}