1672: 迷宫问题（bfs）

解题思路:

注意事项:

参考代码:

#include <iostream>
#include <queue>
using namespace std;
struct node{
	int x;
	int y;
	int step;
	node(int xx,int yy,int sstep){
		x=xx;
		y=yy;
		step=sstep;
	}
};
char s[101][101];
int sx,sy,fx,fy;//起点和终点的横纵坐标
bool vis[101][101];
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int n,m;
bool in(int x,int y){
	return x>=0&&x<n&&y>=0&&y<m;
}
int bfs(int x,int y){
	queue<node> q;
	q.push(node(x,y,0));
	while(!q.empty()){
		node a=q.front();
		q.pop();
		int x=a.x,y=a.y;
		for(int i=0;i<4;i++){
			int tx=x+dir[i][0];
			int ty=y+dir[i][1];
			int tstep=a.step+1;
			if(in(tx,ty)&&!vis[tx][ty]&&s[tx][ty]=='-'){
				vis[tx][ty]=true;
				q.push(node(tx,ty,tstep));
			}
			if(tx==fx&&ty==fy){
				return a.step+1;
			}
		}
	}
	return -1;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>>s[i][j];
				if(s[i][j]=='S'){
					sx=i,sy=j;
				}else if(s[i][j]=='E'){
					fx=i,fy=j;
				}
			}
		}
		cout<<bfs(sx,sy)<<endl;
	}
	return 0;
}