大雨应经下了几天雨,却还是没有停的样子。土豪CCY刚从外地赚完1e元回来,知道不久除了自己别墅,其他的地方都将会被洪水淹没。
CCY所在的城市可以用一个N*M(N,M<=50)的地图表示,地图上有五种符号:“. * X D S”。其中“X”表示石头,水和人都不能从上面经过。“.”表示平原,CCY和洪水都可以经过。“*”表示洪水开始地方(可能有多个地方开始发生洪水)。“D”表示CCY的别墅。“S”表示CCY现在的位置。
CCY每分钟可以向相邻位置移动,而洪水将会在CCY移动之后把相邻的没有的土地淹没(从已淹没的土地)。
求CCY回到别墅的最少时间。如果聪哥回不了家,就很可能会被淹死,那么他就要膜拜黄金大神涨RP来呼叫直升飞机,所以输出“ORZ hzwer!!!”。
输入格式:
3 3 D.*
… .S.
输出格式:
3
输入样例#1:
3 3
D.*
…
..S
输出样例#1:
ORZ hzwer!!!
输入样例#2:
3 6
D…*.
.X.X..
….S.
输出样例#2:
6
很简单的广搜问题,按照题目的要求模拟即可
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 using namespace std;
7 int n,m;
8 int xx[7]={-1,+1,0,0};
9 int yy[7]={0,0,-1,+1};
10 struct peo
11 {
12 int juli;//
13 int x,y;
14 int step;
15 }now,nxt;
16 int map[201][201];
17 int bgx,bgy,homex,homey;
18 int vis[201][201];// 被洪水淹没的地方,注意要map和vis同时判断
19 int ans=438438;
20 int watercishu=1;
21 int flag=0;
22 int vis2[201][201];
23 int calca(int xxx,int yyy)
24 {
25 return max(xxx,homex)-min(xxx,homex)+max(yyy,homey)-min(yyy,homey);
26 }
27 void init()
28 {
29 scanf("%d%d",&n,&m);
30 for(int i=1;i<=n;i++)
31 for(int j=1;j<=m;j++)
32 {
33 char p;
34 cin>>p;
35 if(p=='.')
36 map[i][j]=0;// 都可以通过
37 else if(p=='X')
38 map[i][j]=1;// 都不可以通过
39 else if(p=='S')
40 {map[i][j]=2;//人现在的位置
41 bgx=i;bgy=j;}
42 else if(p=='*')
43 map[i][j]=3,vis[i][j]=1;// 洪水开始的地方
44 else if(p=='D')
45 {
46 map[i][j]=4;// 家
47 homex=i;
48 homey=j;
49 }
50
51 }
52 }
53 void ex()
54 {
55 int flag=0;
56 for(int i=1;i<=n;i++)
57 {
58 for(int j=1;j<=m;j++)
59 {
60 if(vis[i][j]==watercishu)
61 {
62 for(int k=0;k<4;k++)
63 {
64 int wx=i+xx[k];
65 int wy=j+yy[k];
66 if(vis[wx][wy]==0&&map[wx][wy]!=1&&map[wx][wy]!=4&&wx>=1&&wx<=n&&wy>=1&&wy<=m)
67 {
68 vis[wx][wy]=vis[i][j]+1;
69 }
70 }
71 }
72 }
73 }
74 watercishu++;
75 }
76 void bfs()
77 {
78 queue<peo>q;
79 now.x=bgx;now.y=bgy;now.step=0;now.juli=calca(bgx,bgy);
80 q.push(now);
81 int last=0;// 记录上一次洪水扩展时人走的步数
82 while(q.size()!=0)
83 {
84 peo p=q.front();
85 if(vis[p.x][p.y]!=0)
86 {
87 q.pop();
88 continue;
89 }
90 if(p.juli==0)
91 {
92 printf("%d",p.step);
93 flag=1;
94 return ;
95 }
96
97 q.pop();
98 if(p.step>last)
99 {
100 ex();// 洪水扩展
101 last=p.step;
102 }
103 if(vis[p.x][p.y]!=0)
104 {
105 continue;
106 }
107 for(int i=0;i<4;i++)
108 {
109 int wx=p.x+xx[i];
110 int wy=p.y+yy[i];
111 if(vis2[wx][wy]==0&&vis[wx][wy]==0&&map[wx][wy]!=1&&wx>=1&&wx<=n&&wy>=1&&wy<=m)
112 {
113 vis2[wx][wy]=1;
114 nxt.x=wx;
115 nxt.y=wy;
116 nxt.step=p.step+1;
117 nxt.juli=calca(wx,wy);
118 q.push(nxt);
119 }
120 }
121
122 }
123 }
124 int main()
125 {
126 /// freopen("sliker.in","r",stdin);
127 // freopen("sliker.out","w",stdout);
128 init();
129 bfs();
130 if(flag==0)
131 printf("ORZ hzwer!!!");
132 return 0;
133 }