题目描述
大雨应经下了几天雨，却还是没有停的样子。土豪CCY刚从外地赚完1e元回来，知道不久除了自己别墅，其他的地方都将会被洪水淹没。
CCY所在的城市可以用一个N*M(N,M<=50)的地图表示，地图上有五种符号：“. * X D S”。其中“X”表示石头，水和人都不能从上面经过。“.”表示平原，CCY和洪水都可以经过。“*”表示洪水开始地方（可能有多个地方开始发生洪水）。“D”表示CCY的别墅。“S”表示CCY现在的位置。
CCY每分钟可以向相邻位置移动，而洪水将会在CCY移动之后把相邻的没有的土地淹没（从已淹没的土地）。
求CCY回到别墅的最少时间。如果聪哥回不了家，就很可能会被淹死，那么他就要膜拜黄金大神涨RP来呼叫直升飞机，所以输出“ORZ hzwer!!!”。
输入输出格式
输入格式：
3 3
D.*
…
.S.
输出格式：
3
输入输出样例
输入样例#1：
3 3
D.*
…
..S
输出样例#1：
ORZ hzwer!!!
输入样例#2：
3 6
D…*.
.X.X..
….S.
输出样例#2：
6 很简单的广搜问题，按照题目的要求模拟即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int n,m;
int xx[]={-,+,,};
int yy[]={,,-,+};
struct peo
{
int juli;//
int x,y;
int step;
}now,nxt;
int map[][];
int bgx,bgy,homex,homey;
int vis[][];// 被洪水淹没的地方，注意要map和vis同时判断
int ans=;
int watercishu=;
int flag=;
int vis2[][];
int calca(int xxx,int yyy)
{
return max(xxx,homex)-min(xxx,homex)+max(yyy,homey)-min(yyy,homey);
}
void init()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
char p;
cin>>p;
if(p=='.')
map[i][j]=;// 都可以通过
else if(p=='X')
map[i][j]=;// 都不可以通过
else if(p=='S')
{map[i][j]=;//人现在的位置
bgx=i;bgy=j;}
else if(p=='*')
map[i][j]=,vis[i][j]=;// 洪水开始的地方
else if(p=='D')
{
map[i][j]=;// 家
homex=i;
homey=j;
} }
}
void ex()
{
int flag=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(vis[i][j]==watercishu)
{
for(int k=;k<;k++)
{
int wx=i+xx[k];
int wy=j+yy[k];
if(vis[wx][wy]==&&map[wx][wy]!=&&map[wx][wy]!=&&wx>=&&wx<=n&&wy>=&&wy<=m)
{
vis[wx][wy]=vis[i][j]+;
}
}
}
}
}
watercishu++;
}
void bfs()
{
queue<peo>q;
now.x=bgx;now.y=bgy;now.step=;now.juli=calca(bgx,bgy);
q.push(now);
int last=;// 记录上一次洪水扩展时人走的步数
while(q.size()!=)
{
peo p=q.front();
if(vis[p.x][p.y]!=)
{
q.pop();
continue;
}
if(p.juli==)
{
printf("%d",p.step);
flag=;
return ;
} q.pop();
if(p.step>last)
{
ex();// 洪水扩展
last=p.step;
}
if(vis[p.x][p.y]!=)
{
continue;
}
for(int i=;i<;i++)
{
int wx=p.x+xx[i];
int wy=p.y+yy[i];
if(vis2[wx][wy]==&&vis[wx][wy]==&&map[wx][wy]!=&&wx>=&&wx<=n&&wy>=&&wy<=m)
{
vis2[wx][wy]=;
nxt.x=wx;
nxt.y=wy;
nxt.step=p.step+;
nxt.juli=calca(wx,wy);
q.push(nxt);
}
} }
}
int main()
{
/// freopen("sliker.in","r",stdin);
// freopen("sliker.out","w",stdout);
init();
bfs();
if(flag==)
printf("ORZ hzwer!!!");
return ;
}