首页 > 代码库 > 水灾（sliker.cpp/c/pas） 1000MS 64MB

水灾（sliker.cpp/c/pas） 1000MS 64MB

2024-08-21 11:44:34   216人阅读

大雨应经下了几天雨，却还是没有停的样子。土豪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<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int n,m,qsl,qrl,zh,zl,a,b,c,nh,nl;
 5 int qs[2][2600][2],qr[2][2600][2];
 6 int hb[]={0,0,1,-1},lb[]={1,-1,0,0};
 7 char ch;
 8 int map[60][60],rj[60][60];
 9 int main(){
10     scanf("%d%d",&n,&m);
11     for(int i=1;i<=n;i++)
12     for(int j=1;j<=m;j++){
13         cin>>ch;
14         if(ch==‘X‘) map[i][j]=1;
15         if(ch==‘*‘){qs[0][qsl][0]=i;qs[0][qsl++][1]=j;map[i][j]=1;}
16         if(ch==‘S‘){qr[0][qrl][0]=i;qr[0][qrl++][1]=j;rj[i][j]=1;}
17         if(ch==‘D‘){zh=i;zl=j;map[i][j]=1;}
18     }
19     for(int ans=1;;ans++){
20         if(!qrl) break;
21         b=(ans+1)%2;c=ans%2;
22         for(int i=0;i<qsl;i++){
23             for(int j=0;j<4;j++){
24                 nh=qs[b][i][0]+hb[j];nl=qs[b][i][1]+lb[j];
25                 if(!map[nh][nl]&&nh>0&&nh<=n&&nl>0&&nl<=m){
26                     map[nh][nl]=1;
27                     qs[c][a][0]=nh;qs[c][a++][1]=nl;
28                 }
29             }
30         }
31         qsl=a;a=0;
32         for(int i=0;i<qrl;i++){
33             for(int j=0;j<4;j++){
34                 nh=qr[b][i][0]+hb[j];nl=qr[b][i][1]+lb[j];
35                 if(nh==zh&&nl==zl){printf("%d\n",ans);return 0;}
36                 if(!rj[nh][nl]&&!map[nh][nl]&&nh>0&&nh<=n&&nl>0&&nl<=m){
37                     rj[nh][nl]=1;
38                     qr[c][a][0]=nh;qr[c][a++][1]=nl;
39                 }
40             }
41         }
42         printf("\n");
43         qrl=a;a=0;
44     }
45     printf("ORZ hzwer!!!\n");
46     return 0;
47 }
View Code
這道題有數據坑，不按描述的來，得了90~

水灾（sliker.cpp/c/pas） 1000MS 64MB


联系
我们