首页 > 代码库 > 水灾 1000MS 64MB (广搜)
水灾 1000MS 64MB (广搜)
水灾（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
3
Input
3 3
D.*
…
..S
Output
ORZ hzwer!!!
Input
3 6
D…*.
.X.X..
….S.
Output
6
分析：找出洪水开始的所有节点，写两个广搜，另一个搜索洪水走的路线bfs_1,一个搜索人走的路线 bfs_2。
在bfs_2中，人每走一步之前，先bfs_1搜索洪水下一秒将要淹没点，然后搜索人走的路线。
1 #include<cstdio> 2 #include<algorithm> 3 #include<queue> 4 #include<cstring> 5 #include<iostream> 6 7 using namespace std; 8 const int N = 110; 9 10 struct node{11 int x,y,step;12 }cur,nxt,t,u;13 14 queue <node> q;15 queue <node> q2;16 int mp[N][N];17 bool v[N][N],v2[N][N];18 int dx[5] = {0,1,0,-1};19 int dy[5] = {1,0,-1,0};20 int n,m,ex,ey,sx,sy,now;21 char ch;22 23 void bfs_1(int w) //搜出w+1秒的地图 24 {25 while(!q.empty())26 {27 cur = q.front();28 if(cur.step!=w) return ;29 q.pop();30 for(int i=0;i<4;++i)31 {32 int a = dx[i]+cur.x;33 int b = dy[i]+cur.y;34 if(a>0 && b>0 && a<=n && b<=m && mp[a][b]==1 && !v[a][b])35 {36 if(a==ex && b==ey) continue;37 mp[a][b] = 0;38 v[a][b] = true;39 nxt.x = a; nxt.y = b; nxt.step = cur.step+1;40 q.push(nxt);41 }42 }43 }44 }45 void bfs_2()46 {47 now = 0;48 bfs_1(now);49 t.x = sx; t.y = sy; t.step = 0;50 q2.push(t);51 v2[sx][sy] = true;52 while(!q2.empty())53 {54 t = q2.front();55 if(t.step!=now) 56 {now++; bfs_1(now); continue;}57 q2.pop();58 for(int i=0;i<4;++i)59 {60 int a = dx[i]+t.x;61 int b = dy[i]+t.y;62 if(a>0 && b>0 && a<=n && b<=m && mp[a][b]==1 && !v2[a][b])63 {64 if(a==ex && b==ey)65 {66 printf("%d\n",t.step+1);return ;67 }68 v2[a][b] = true;69 u.x = a; u.y = b; u.step = t.step+1;70 q2.push(u);71 }72 }73 }74 printf("ORZ hzwer!!!\n");75 }76 int main()77 {78 freopen("sliker.in","r",stdin);79 freopen("sliker.out","w",stdout);80 scanf("%d%d",&n,&m);81 for(int i=1;i<=n;++i)82 for(int j=1;j<=m;++j)83 {84 cin>>ch;85 if(ch==‘S‘) sx=i,sy=j,mp[i][j]=1;86 else if(ch==‘D‘) ex=i,ey=j,mp[i][j]=1;87 else if(ch==‘*‘)88 {89 mp[i][j] = 0;90 v[i][j] = true;91 cur.x = i; cur.y = j; cur.step = 0;92 q.push(cur); 93 }94 else if(ch==‘.‘) mp[i][j] = 1;95 else if(ch==‘X‘) mp[i][j] = 3;96 }97 bfs_2();98 return 0; 99 }
水灾 1000MS 64MB (广搜)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。