水灾

　　　　　　　　（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
Input1
3 3
D.*
...
.S.

Output1
3

Input2
3 3
D.*
...
..S

Output2
ORZ hzwer!!!

Input3
3 6
D...*.
.X.X..
....S.

Output3
6

#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
string s[51];
int n,m,xx[4]={1,0,0,-1},yy[4]={0,1,-1,0};
int mp[51][51],mmp[51][51];
int ex,ey,sx,sy,ans=0,bex,bey;
bool f[51][51]={0},map[51][51];
queue<int> dx,dy,stx,sty;
bool g;
bool pan(int a,int b){
    return (a>=0&&a<n&&b>=0&&b<m);
}
void bfs(int x){//计算各个能到达的点洪水到达的时间 
    int t=dy.size();
    while(t){
        sx=dx.front();dx.pop();
        sy=dy.front();dy.pop();
        map[sx][sy]=0;
        mp[sx][sy]=x;
        for(int i=0;i<4;i++){
            int a=sx+xx[i],b=sy+yy[i];
            if(pan(a,b)&&map[a][b]&&mp[a][b]>x+1){
                dx.push(a);
                dy.push(b);
                map[a][b]=0;
            }
        }
        t--;
    }
    if(!dx.empty()) bfs(x+1);
}
void bfs1(int x,int y){//宽搜人到达没有洪水的各点的时间，并记录是否到达公寓 
    mmp[x][y]=0;
    stx.push(x);
    sty.push(y);
    f[x][y]=0;
    while(!stx.empty()){
        sx=stx.front();
        sy=sty.front();
        f[sx][sy]=0;
        stx.pop();
        sty.pop();
        if(sx==ex&&sy==ey){
            ans=mmp[ex][ey];
            return;
        }
        for(int i=0;i<4;i++){
            int a=sx+xx[i],b=sy+yy[i];
            if(pan(a,b)&&f[a][b]&&mmp[sx][sy]+1<mp[a][b]){
                mmp[a][b]=mmp[sx][sy]+1;
                f[a][b]=0;
                stx.push(a);
                sty.push(b);
            }
        }
    }
}
int main(){
    freopen("sliker.in","r",stdin);
    freopen("sliker.out","w",stdout);
    scanf("%d%d",&n,&m);
    getchar();
    for(int i=0;i<n;i++) 
     getline(cin,s[i]);
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++) mp[i][j]=2147483647;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++){
        if(s[i][j]=='.') f[i][j]=1,map[i][j]=1;
        if(s[i][j]=='*'){
            dx.push(i);
            dy.push(j);
        }
        if(s[i][j]=='D'){ex=i;ey=j;}
        if(s[i][j]=='S'){bex=i,bey=j;}
    }
    map[bex][bey]=f[bex][bey]=1;
    map[ex][ey]=0;
    bfs(0);
    f[ex][ey]=1;
    bfs1(bex,bey);
    if(ans!=0) printf("%d
",ans);
    else printf("ORZ hzwer!!!
");
    fclose(stdin);
    fclose(stdout);
    return 0;
}

View Code