首页 > 代码库 > T4870 水灾（sliker.cpp/c/pas） 1000MS 64MB
T4870 水灾（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!!!”。
输入输出格式
输入格式：3 3D.*
….S.
输出格式：3
输入输出样例
输入样例#1：
3 3D.*…..S
输出样例#1：
ORZ hzwer!!!
输入样例#2：
3 6D…*..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 }
T4870 水灾（sliker.cpp/c/pas） 1000MS 64MB
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。