本文主要是介绍洪水,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Description
一天, 一个画家在森林里写生,突然爆发了山洪,他需要尽快返回住所中,那里是安
全的。
森林的地图由R行C列组成,空白区域用点“.”表示,洪水的区域用“*”表示,而
岩石用“X”表示,另画家的住所用“D”表示,画家用“S”表示。
有以下几点需要说明:
1、 每一分钟画家能向四个方向移动一格(上、下、左、右)
2、 每一分钟洪水能蔓延到四个方向的相邻格子(空白区域)
3、 洪水和画家都不能通过岩石区域
4、 画家不能通过洪水区域(同时也不行,即画家不能移到某个格子,该格子在画家达到的同时被洪水蔓延到了,这也是不允许的)
5、 洪水蔓不到画家的住所。
给你森林的地图,编写程序输出最少需要花费多长时间才能从开始的位置赶回家中。
Input
输入第一行包含两个整数R和C(R,C<=50)。
接下来R行每行包含C个字符(“.”、“*”、“X”、“D”或“S”)。地图保证只有一个“D”和一个“S”。
Output
输出画家最快安全到达住所所需的时间,如果画家不可能安全回家则输出“KAKTUS”。
Sample Input
输入1:
3 3
D.*
…
.S.
输入2:
3 3
D.*
…
…S
输入3:
3 6
D…*.
.X.X…
…S.
Sample Output
输出1:
3
输出2:
KAKTUS
输出3:
6
.
.
.
.
.
.
分析
大水题
bfs
先记录洪水漫延的时间点
再做画家的bfs,判断到某个点的时间即可
.
.
.
.
.
.
程序:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;int r,c,h,bx,by,ex,ey,n,n1,fx[2600],fy[2600],gx[2600],gy[2600];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool bz=false,b[60][60],a[210][60][60];void check(char ch,int x,int y)
{if (ch=='D'){ex=x;ey=y;b[x][y]=true;}if (ch=='S'){bx=x;by=y;b[x][y]=true;}if (ch=='.') b[x][y]=true;if (ch=='X') b[x][y]=false;if (ch=='*'){n++;fx[n]=x;fy[n]=y;}
}void bfs()
{int head=0,tail=1,t,s,g[125010][3];bool flag[60][60];memset(g,0,sizeof(g));memcpy(flag,b,sizeof(b));head=0;tail=1;g[1][0]=bx;g[1][1]=by;g[1][2]=1;while (head<tail){head=head%2500+1;for (int i=0;i<=3;i++){int nx=g[head][0]+dx[i],ny=g[head][1]+dy[i];t=g[head][2];if (t>h) return;if (flag[nx][ny]==true&&a[t][nx][ny]==true&&nx>0&&nx<=r&&ny>0&&ny<=c){tail=tail%2500+1;g[tail][0]=nx;g[tail][1]=ny;g[tail][2]=t+1;flag[nx][ny]=false;if (nx==ex&&ny==ey){printf("%d",t);bz=true;return;}}}if (t>10) s++;}
}int main()
{scanf("%d%d",&r,&c);for (int i=1;i<=r;i++)for (int j=1;j<=c;j++){char ch;cin>>ch;check(ch,i,j);}h=r*2+c*2;memcpy(a[0],b,sizeof(b));for (int i=1;i<=h;i++){n1=0;memset(gx,0,sizeof(gx));memset(gy,0,sizeof(gy));memcpy(a[i],a[i-1],sizeof(a[i-1]));for (int j=1;j<=n;j++)for (int k=0;k<=4;k++)if (a[i][fx[j]+dx[k]][fy[j]+dy[k]]==true&&fx[j]+dx[k]>0&&fx[j]+dx[k]<=r&&fy[j]+dy[k]>0&&fy[j]+dy[k]<=c&&!(fx[j]+dx[k]==ex&&fy[j]+dy[k]==ey)){a[i][fx[j]+dx[k]][fy[j]+dy[k]]=false;n1++;gx[n1]=fx[j]+dx[k];gy[n1]=fy[j]+dy[k];}n=n1;memcpy(fx,gx,sizeof(gx));memcpy(fy,gy,sizeof(gy));}bfs();if (bz==false) printf("KAKTUS");return 0;
}
这篇关于洪水的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!