2179: 信息学奥赛一本通T1256-献给阿尔吉侬的花束

解题思路: 标准BFS ， 数组实现Que

注意事项:计算距离时, nd.x, nd.y 不是x， y

参考代码:

#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e2 + 10;
int g[N][N],t,r,c,sx,sy,ex,ey,dis[N][N];
bool v[N][N];
int d[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
struct node {
	int x, y;
};
node que[N*N];
int tt = -1, ff = 0;
void bfs(int x, int y){
	que[++tt] = {x, y};
	while(ff <= tt){
		node nd = que[ff++];
		for(int i = 0; i < 4; i ++){
			int nx = nd.x + d[i][0];
			int ny = nd.y + d[i][1];
			if(nx >= 0 && nx < r && ny >= 0 && ny < c && !v[nx][ny] && !g[nx][ny]){
				v[nx][ny] = true;
				if(dis[nx][ny] > dis[nd.x][nd.y] + 1) dis[nx][ny] = dis[nd.x][nd.y] + 1;
				que[++tt] = {nx,ny};
			}
		}
	}
}
int main()
{
	cin >>t;
	while(t--){
		memset(dis,0x3f, sizeof(dis));
		memset(g,0,sizeof(g));
		memset(v,0,sizeof(v));
		cin >> r >> c;
		for(int i = 0; i < r; i ++ )
			for(int j = 0; j < c; j ++)
			 {
			 	char c;
			 	cin >> c;
			 	if(c == 'S'){
			 		sx = i;
			 		sy = j;
				}
				else if (c == '#') g[i][j] = 1;
				else if (c == 'E') {
					ex = i;
					ey = j;
				}
			 }
		dis[sx][sy] = 0;
		v[sx][sy] = true;
		bfs(sx, sy);
		if(dis[ex][ey] < 0x3f3f3f3f) cout << dis[ex][ey] << endl;
		else cout << "oop!" << endl;
		tt = -1, ff = 0;	
	}
	return 0;
}