NOIP模拟赛水灾

大雨应经下了几天雨，却还是没有停的样子。土豪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

Input

3 3

D.*
…

..S

Output

ORZ hzwer!!!

Input

3 6

D…*.

.X.X..

....S.

Output

 #include<iostream>

 #include<queue>

 #include<cstring>

 using namespace std;

 const int INF=0x7f7f7f7f;

 int n,m,sx,sy,tx,ty;

 char map[][];

 int T[][];

 int xx[]={-,,,};

 int yy[]={,,,-};

 char ch[];

 struct data{int x,y,t;};

 void bfs1()

 {

     queue<data> Q;

     data p;

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             if(map[i][j]=='*')

             {

                 p=(data){i,j};

                 T[i][j]=;

                 Q.push(p);

             }

     while(!Q.empty())

     {

         p=Q.front();Q.pop();

         for(int i=;i<;i++)

         {

             int x=p.x+xx[i],y=p.y+yy[i];

             if(x<||x>n||y<||y>m||T[x][y]!=INF) continue;

             T[x][y]=T[p.x][p.y]+;

             Q.push((data){x,y});

         }

     }

 }

 void bfs2()

 {

     bool vis[][],flag=;

     memset(vis,,sizeof(vis));

     queue<data> Q;

     data p={sx,sy,};vis[sx][sy]=;

     Q.push(p);

     while(!Q.empty())

     {

         p=Q.front();Q.pop();

         if(p.x==tx&&p.y==ty) {flag=;break;}

         for(int i=;i<;i++)

         {

             int x=p.x+xx[i],y=p.y+yy[i];

             if(x<||x>n||y<||y>m||T[x][y]<=p.t+||vis[x][y]) continue;

             vis[x][y]=;

             Q.push((data){x,y,p.t+});

         }

     }

     if(flag) printf("%d\n",p.t);

     else printf("ORZ hzwer!!!\n");

 }

 int main()

 {

     scanf("%d %d",&n,&m);

     memset(T,0x7f,sizeof(T));

     for(int i=;i<=n;i++)

     {

         scanf("%s",ch+);

         for(int j=;j<=m;j++)

         {

             map[i][j]=ch[j];

             switch(map[i][j])

             {

             case 'S':

                 sx=i,sy=j;

                 break;

             case 'D':

                 tx=i,ty=j;

                 T[i][j]=INF-;

                 break;

             case 'X':

                 T[i][j]=;

                 break;

             }

         }

     }

     bfs1();

     bfs2();

     return ;

 }

双重bfs

巴特西

NOIP模拟赛水灾

最新文章

热门文章

巴特西

NOIP模拟赛 水灾

最新文章

热门文章

NOIP模拟赛水灾