水灾（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!!!”。

Input

3 3

D.*

…

.S.

Output

3

Input

3 3

D.*
…

..S

Output

ORZ hzwer!!!

Input

3 6

D…*.

.X.X..

….S.

Output

6

大模拟，本来想用深搜加上回溯，疯狂模拟了两个小时，结果tle了九个。。。。。

然后考虑怎么优化，我们发现，ccy每走一步，洪水就扩散一下，这样不适合使用深搜，不然你要一次次扩散，再一次次将扩散的退去。

那么怎么办，我们考虑，ccy每步要走的地方是固定的几个点，那么我们就将那可以走的点标记，然后再将洪水扩散，再讲他的步伐扩散，

其实就是广搜。将洪水与ccy的步伐分别扩散，当ccy的步伐扩散到别墅时停止，用个数组记录他每步是第几步，再就是一些细节的地方

需要自己调试，思路明白就很好做了。

附上代码

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<string>
  4 #include<queue>
  5 using namespace std;
  6 int n,m,a[55][55],x,y,ans[55][55],js,dq,hs=4,jj=-1;
  7 bool bz;
  8 queue <int>qx;
  9 queue <int>qy;
 10 string c;
 11 int main()
 12 {
 13     scanf("%d%d",&n,&m);
 14     for(int j=1;j<=n;++j)
 15     {
 16         cin>>c;
 17         for(int i=0;i<m;++i)
 18         {
 19             if(c[i]=='.') a[j][i+1]=1;//1表示平原
 20             if(c[i]=='D')
 21             a[j][i+1]=2;//2表示别墅
 22             if(c[i]=='S')
 23             {
 24                 a[j][i+1]=3;//3表示人
 25                 x=j,y=i+1;
 26             }
 27              
 28             if(c[i]=='*') a[j][i+1]=4;//4表示洪水 
 29         }
 30     }
 31     qx.push(x);
 32     qy.push(y);
 33     while(!qx.empty())
 34     {
 35         x=qx.front();
 36         y=qy.front();
 37         qx.pop();
 38         qy.pop();
 39         if(a[x][y]>=4) continue;
 40         if(a[x+1][y]==2||a[x-1][y]==2||a[x][y+1]==2||a[x][y-1]==2)
 41         {
 42             js=ans[x][y]+1;
 43             break;
 44         }
 45         if(a[x+1][y]==1)
 46         {
 47             qx.push(x+1);
 48             qy.push(y);
 49             a[x+1][y]=3;
 50             ans[x+1][y]=ans[x][y]+1;
 51         }
 52         if(a[x-1][y]==1)
 53         {
 54             qx.push(x-1);
 55             qy.push(y);
 56             a[x-1][y]=3;
 57             ans[x-1][y]=ans[x][y]+1;
 58         }
 59         if(a[x][y+1]==1)
 60         {
 61             qx.push(x);
 62             qy.push(y+1);
 63             a[x][y+1]=3;
 64             ans[x][y+1]=ans[x][y]+1;
 65         }
 66         if(a[x][y-1])
 67         {
 68             qx.push(x);
 69             qy.push(y-1);
 70             a[x][y-1]=3;
 71             ans[x][y-1]=ans[x][y]+1;
 72         }
 73         bz=0;
 74         if(ans[x][y]<=jj) 
 75         {
 76             continue;    
 77         }
 78         jj=ans[x][y];
 79         for(int i=1;i<=n;++i)
 80         {
 81             for(int j=1;j<=m;++j)
 82             {
 83                 if(a[i][j]==hs)
 84                 {
 85                     if(a[i+1][j]==1||a[i+1][j]==3)
 86                     a[i+1][j]=hs+1,bz=1;
 87                     if(a[i-1][j]==1||a[i-1][j]==3)
 88                     a[i-1][j]=hs+1,bz=1;
 89                     if(a[i][j+1]==1||a[i][j+1]==3)
 90                     a[i][j+1]=hs+1,bz=1;
 91                     if(a[i][j-1]==1||a[i][j-1]==3)
 92                     a[i][j-1]=hs+1,bz=1;
 93                 }
 94             }
 95         }
 96         if(bz==1) ++hs;
 97      } 
 98      if(js==0)
 99      printf("ORZ hzwer!!!");
100      else
101      printf("%d",js);
102     return 0;
103 }