[noip模拟]水灾<BFS>-白红宇

[noip模拟]水灾<BFS>

阅读量：7049 次

发布时间：2019-06-28

本文共 5783 字，大约阅读时间需要 19 分钟。

水灾（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

Input

3 3

D.*

…

..S

Output

ORZ hzwer!!!

Input

3 6

D...*.

.X.X..

....S.

Output

-----------------------------------------------------------------------------------------------------------------------------------------

其实我相信所有人看见这道题都会想到BFS，而且会觉得很简单，我也不例外，但是我竟然还是错了5组数据，四组崩溃，一组WA，我一开始是以为我的BFS写挂了致使空间爆了

在加上之前的几道BFS都挂了，所以我一度对自己的BFS失去信心，直到现在才发现这道题错了纯属自己犯二。。。。。

这道题的思路很好想的，就是跑个BFS，只是有一点与正常BFS有些出入，就是在每一层运行时，要把所有时间点相同（即是要同一时刻的水和人遍历完后才运行下一层）

然后还要一点就是要先跑洪水再走人，因为如果人先走了，但是同时水也淹没了这个位置，那这个位置就是不能去的，但是先走人会把这个点标记成有人（当然这个可以后期处理，不过先水再人可以更好的理解，推荐用这种）

然后还有一个小细节就是要对存水的队列判空，要不为空的时候才继续让水蔓延，否则会崩溃（如果存水的队列在为空时没有跳出，就会让程序崩溃，感兴趣的可以试试QAQ）

好了接下来就是发这个让我崩溃很久的水题的代码

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #define maxn 70 10 using namespace std; 11 12 const int dx[]={-1,1,0,0}; 13 const int dy[]={ 0,0,-1,1}; 14 15 struct node{ 16 int x,y,cnt; 17 }; 18 19 queue
              
               flood; 20 queue
               
                ccy; 21 22 int n,m,map[maxn][maxn],tot; 23 int sx,sy,fx,fy,real; 24 25 int back() 26 { 27 for(int i=0;i<4;i++) 28 { 29 int ox=fx+dx[i],oy=fy+dy[i]; 30 if(ox<1||ox>n||oy<1||oy>m)continue; 31 if(map[ox][oy]==0||map[ox][oy]==2)return false;//可以回家 32 } 33 return true; 34 } 35 36 void people() 37 { 38 int zx=0,zy=0; 39 node f=ccy.front(); 40 int tt=f.cnt; 41 while(tt==f.cnt){ 42 f=ccy.front(); 43 ccy.pop(); 44 for(int i=0;i<4;i++) 45 { 46 zx=f.x+dx[i];zy=f.y+dy[i]; 47 if(map[zx][zy]==1||map[zx][zy]==-1||map[zx][zy]==2)continue; 48 if(zx<1||zx>n||zy<1||zy>m)continue; 49 map[zx][zy]=2; 50 ccy.push((node){zx,zy,f.cnt+1}); 51 if(zx==fx&&zy==fy) 52 { 53 printf("%d ",f.cnt+1);real=1;return; 54 } 55 } 56 f=ccy.front(); 57 } 58 } 59 60 void water() 61 { 62 int zx=0,zy=0; 63 if(!flood.empty()) 64 { 65 node e=flood.front(); 66 int cn=e.cnt; 67 while(e.cnt==cn) 68 { 69 e=flood.front(); 70 flood.pop(); 71 for(int i=0;i<4;i++) 72 { 73 zx=e.x+dx[i];zy=e.y+dy[i]; 74 if(map[zx][zy]==-1||map[zx][zy]==1)continue; 75 if(zx<1||zx>n||zy<1||zy>m)continue; 76 if(zx==fx&&zy==fy)continue; 77 map[zx][zy]=1; 78 flood.push((node){zx,zy,e.cnt+1}); 79 } 80 e=flood.front(); 81 } 82 } 83 } 84 85 void read(){ 86 scanf("%d%d",&n,&m); 87 for(int i=1;i<=n;i++) 88 { 89 char c[55]; 90 scanf("%s",c); 91 for(int j=0;j