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

3

Input

3 3

D.*

…

..S

Output

ORZ hzwer!!!

Input

3 6

D…*.

.X.X..

….S.

Output

6

1 #include
         
            2 #include
          
             3 #include
           
              4 #include
            
               5 #define maxn 60  6 using namespace std;  7 int n,m,ex,ey;  8 int d[maxn][maxn],dis[maxn][maxn],f[maxn][maxn];  9 char a[maxn][maxn]; 10 int b[5]={
       0,0,1,0,-1}; 11 int c[5]={
       0,1,0,-1,0}; 12 queue
             
              qx; 13 queue
              
               qy; 14 void spfa(int x,int y) 15 { 16 int i,j,k; 17 memset(f,0,sizeof(f)); 18 d[x][y]=0; 19 qx.push(x); 20 qy.push(y); 21 f[x][y]=1; 22 while(!qx.empty()) 23 { 24 int nx=qx.front(); 25 int ny=qy.front(); 26 qx.pop(); 27 qy.pop(); 28 f[nx][ny]=0; 29 for(i=1;i<=4;i++) 30 { 31 int xx=nx+b[i]; 32 int yy=ny+c[i]; 33 if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&(a[xx][yy]!='X'&&a[xx][yy]!='D')) 34 { 35 if(d[xx][yy]>d[nx][ny]+1) 36 { 37 d[xx][yy]=d[nx][ny]+1; 38 if(!f[xx][yy]) 39 { 40 f[xx][yy]=1; 41 qx.push(xx); 42 qy.push(yy); 43 } 44 } 45 } 46 } 47 } 48 } 49 void SPFA(int x,int y) 50 { 51 int i,j,k; 52 memset(f,0,sizeof(f)); 53 dis[x][y]=0; 54 qx.push(x); 55 qy.push(y); 56 f[x][y]=1; 57 while(!qx.empty()) 58 { 59 int nx=qx.front(); 60 int ny=qy.front(); 61 qx.pop(); 62 qy.pop(); 63 f[nx][ny]=0; 64 for(i=1;i<=4;i++) 65 { 66 int xx=nx+b[i]; 67 int yy=ny+c[i]; 68 if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&(a[xx][yy]!='X')) 69 { 70 if(dis[nx][ny]+1>=d[xx][yy]) 71 continue; 72 if(dis[xx][yy]>dis[nx][ny]+1) 73 { 74 dis[xx][yy]=dis[nx][ny]+1; 75 if(!f[xx][yy]) 76 { 77 f[xx][yy]=1; 78 qx.push(xx); 79 qy.push(yy); 80 } 81 } 82 } 83 } 84 } 85 } 86 int main() 87 { 88 freopen("sliker.in","r",stdin); 89 freopen("sliker.out","w",stdout); 90 int i,j,k; 91 scanf("%d%d",&n,&m); 92 for(i=1;i<=n;i++) 93 scanf("%s",a[i]+1); 94 memset(d,127/3,sizeof(d)); 95 memset(dis,127/3,sizeof(dis)); 96 for(i=1;i<=n;i++) 97 { 98 for(j=1;j<=m;j++) 99 {100 if(a[i][j]=='*')101 spfa(i,j);102 }103 }104 for(i=1;i<=n;i++)105 {106 for(j=1;j<=m;j++)107 {108 if(a[i][j]=='S')109 SPFA(i,j);110 if(a[i][j]=='D')111 ex=i,ey=j;112 }113 }114 if(dis[ex][ey]
View Code