题目

★实验任务

有一只小仓鼠身处在一个 N*M 迷宫之中，它现在想知道它最快能什么时候到达出口。

迷宫是由 ‘ . ’ ‘ # ’ 构成，’ . ’表示可以通行，‘#’表示墙壁，不能通行，现在小仓鼠在‘S’的位置上，问到出口’E’的最短时间是多少？

★数据输入

第一行两个整数 n,m(1<n,m<=1000)表示 n 行，m 列

接下来输入一个 n*m 的迷宫(只包含 ’ . ’ , ’ # ’, ’ S ’,’ E ’)

★数据输出

如果能到达则输出最短时间，否则输出-1。

样例1 输入：

3 4
....
S.#.
.#.E

样例1输出：

6

样例2输出：

3 5
..#..
#S#.E
...#.

样例2输出：

-1

解题思路：

使用队列辅助的宽搜算法，用t作为同步计数器，进行每一层搜索出队，将下一层的位置压入队列，直到出口或者队列为空结束。

解题代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int pd[1005][1005];
int mapp[1005][1005];
struct Node{
	int x,y;
	int count;
};
queue<Node> q;
int x[4]={0,0,1,-1};
int y[4]={1,-1,0,0};
int x1,x2,y11,y2;
int ans=-1;

void bfs(int t){
	Node tt;
	if(q.empty()) return ;
	tt=q.front();
	while(tt.count==t){
		q.pop();
		int xx=tt.x;
		int yy=tt.y;
		int xxx,yyy;
		for(int i=0;i<4;i++){
			xxx=xx+x[i];
			yyy=yy+y[i];
			if(xxx>=1&&yyy>=1&&xxx<=n&&yyy<=m&&pd[xxx][yyy]==1){
				Node ttt;
				ttt.count=t+1;
				ttt.x=xxx;
				ttt.y=yyy;
				pd[xxx][yyy]=0;
				mapp[xxx][yyy]=t+1;
				q.push(ttt);	
				if(xxx==x2&&yyy==y2){
					ans=t;
					return ;
				}
			}
		}			
		tt=q.front();
	}
	bfs(t+1);
}

int main(){
	cin>>n>>m;
	memset(mapp,1,sizeof(mapp));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char a;
			cin>>a;
			if(a=='.') pd[i][j]=1;
			if(a=='#') pd[i][j]=0;
			if(a=='S'){
				pd[i][j]=1;
				x1=i;y11=j;
			} 
			if(a=='E'){
				pd[i][j]=1;
				x2=i;y2=j;
			}
		}
	}
	pd[x1][y11]=0;
	Node r;
	r.x=x1;
	r.y=y11;
	r.count=1;
	q.push(r);
	bfs(1);
	cout<<ans;
	return 0;
}