soj 1754. 逃离洞穴

题意：

一个人在洞穴中做实验，洞穴里面有若干毒气源，毒气源同时向四周（上下左右）以1个单位距离每单位时间散发毒气。这个人在毒气散发的瞬间以1个单位距离每单位时间逃离。问这个人能否逃离洞穴，如果能，那么最短多少单位时间能逃离洞穴。（碰到出口的毒气会散失）

思路：

bfs，与普通宽搜不同的是，在每重循环里面，把这个人走的step相同的所有状态全部出队列扩展，毒气走的step相同的状态也全部出队列扩展，毒气扩展在这个人走位扩展之前进行（多个毒气源）。（可能多个出口？）

代码：

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define N 1005

int sx, sy, r, c, ans;
char data[N][N];
bool vis[N][N];
struct Point
{
	int x, y, step;
	Point() {}
	Point(int _x, int _y, int _s): x(_x), y(_y), step(_s) {}
	bool legal() { return x>0&&x<=r && y>0&&y<=c && data[x][y]=='.'; }
	bool desti() { return data[x][y] == 'E'; }
	bool visit() { return vis[x][y]; }
	void setGas() { data[x][y] = 'D'; }
	void setVis() { vis[x][y] = true; }
};
queue <Point> gas;
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int bfs()
{
	queue <Point> Q;
	Q.push(Point(sx,sy,0));
	vis[sx][sy] = true;
	int gs;
	Point cur, nxt;
	while (!Q.empty())
	{
		if (!gas.empty()) gs = gas.front().step;
		while (!gas.empty() && gas.front().step == gs)
		{
			cur = gas.front();
			gas.pop();
			for (int i = 0; i < 4; ++ i)
			{
				nxt = Point(cur.x+dir[i][0], cur.y+dir[i][1], cur.step+1);
				if (nxt.legal())
				{
					gas.push(nxt);
					nxt.setGas();
				}
			}
		}
		
		if (!Q.empty()) gs = Q.front().step;
		while (!Q.empty() && Q.front().step == gs)
		{
			cur = Q.front();
			Q.pop();
			for (int i = 0; i < 4; ++ i)
			{
				nxt = Point(cur.x+dir[i][0], cur.y+dir[i][1], cur.step+1);
				if (nxt.desti()) return nxt.step;
				if (nxt.legal() && !nxt.visit())
				{
					Q.push(nxt);
					nxt.setVis();
				}
			}
		}
	}
	return -1;
}
int main()
{
	while (scanf("%d %d", &r, &c), r, c)
	{
		memset(vis, false, sizeof(vis));
		while (!gas.empty()) gas.pop();
		for (int i = 1; i <= r; ++ i)
		{
			scanf("%s", data[i]+1);
			for (int j = 1; j <= c; ++ j)
			{
				if (data[i][j] == 'D') gas.push(Point(i,j,0));
				else if (data[i][j] == 'P')
				{
					data[i][j] = '.';
					sx = i; sy = j;
				}
			}
		}
		ans = bfs();
		if (ans == -1) printf("YYR is extremely dangerous!\n");
		else printf("%d\n", ans);
	}
}