水灾（sliker.cpp/c/pas） 1000MS 64MB
大雨应经下了几天雨，却还是没有停的样子。土豪CCY刚从外地赚完1e元回来，知道不久除了自己别墅，其他的地方都将会被洪水淹没。
CCY所在的城市可以用一个N*M(N,M<=50)的地图表示，地图上有五种符号：“. * X D S”。其中“X”表示石头，水和人都不能从上面经过。“.”表示平原，CCY和洪水都可以经过。“*”表示洪水开始地方（可能有多个地方开始发生洪水）。“D”表示CCY的别墅。“S”表示CCY现在的位置。
CCY每分钟可以向相邻位置移动，而洪水将会在CCY移动之后把相邻的没有的土地淹没（从已淹没的土地）。
求CCY回到别墅的最少时间。如果聪哥回不了家，就很可能会被淹死，那么他就要膜拜黄金大神涨RP来呼叫直升飞机，所以输出“ORZ hzwer!!!”。
输入文件 sliker.in
输出文件 sliker.out
Input
3 3
D.*
…
.S.
Output
3
Input
3 3
D.*
…
..S
Output
ORZ hzwer!!!
Input
3 6
D…*.
.X.X..
….S.
Output
6
分析：找出洪水开始的所有节点，写两个广搜，另一个搜索洪水走的路线bfs_1,一个搜索人走的路线 bfs_2。
在bfs_2中，人每走一步之前，先bfs_1搜索洪水下一秒将要淹没点，然后搜索人走的路线。
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<iostream> using namespace std;
const int N = ; struct node{
int x,y,step;
}cur,nxt,t,u; queue <node> q;
queue <node> q2;
int mp[N][N];
bool v[N][N],v2[N][N];
int dx[] = {,,,-};
int dy[] = {,,-,};
int n,m,ex,ey,sx,sy,now;
char ch; void bfs_1(int w) //搜出w+1秒的地图
{
while(!q.empty())
{
cur = q.front();
if(cur.step!=w) return ;
q.pop();
for(int i=;i<;++i)
{
int a = dx[i]+cur.x;
int b = dy[i]+cur.y;
if(a> && b> && a<=n && b<=m && mp[a][b]== && !v[a][b])
{
if(a==ex && b==ey) continue;
mp[a][b] = ;
v[a][b] = true;
nxt.x = a; nxt.y = b; nxt.step = cur.step+;
q.push(nxt);
}
}
}
}
void bfs_2()
{
now = ;
bfs_1(now);
t.x = sx; t.y = sy; t.step = ;
q2.push(t);
v2[sx][sy] = true;
while(!q2.empty())
{
t = q2.front();
if(t.step!=now)
{now++; bfs_1(now); continue;}
q2.pop();
for(int i=;i<;++i)
{
int a = dx[i]+t.x;
int b = dy[i]+t.y;
if(a> && b> && a<=n && b<=m && mp[a][b]== && !v2[a][b])
{
if(a==ex && b==ey)
{
printf("%d\n",t.step+);return ;
}
v2[a][b] = true;
u.x = a; u.y = b; u.step = t.step+;
q2.push(u);
}
}
}
printf("ORZ hzwer!!!\n");
}
int main()
{
freopen("sliker.in","r",stdin);
freopen("sliker.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
{
cin>>ch;
if(ch=='S') sx=i,sy=j,mp[i][j]=;
else if(ch=='D') ex=i,ey=j,mp[i][j]=;
else if(ch=='*')
{
mp[i][j] = ;
v[i][j] = true;
cur.x = i; cur.y = j; cur.step = ;
q.push(cur);
}
else if(ch=='.') mp[i][j] = ;
else if(ch=='X') mp[i][j] = ;
}
bfs_2();
return ;
}