[BFS]洪水

本文主要是介绍[BFS]洪水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

一天， 一个画家在森林里写生，突然爆发了山洪，他需要尽快返回住所中，那里是安
全的。
森林的地图由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.

分析

这题其实很简单，洪水单独一个队列bfs，画家一个队列bfs，然后判断画家到某格时深度是否比洪水深，深就不能过了，然后每个点只用走一次，因为宽度优先搜索先搜到的深度一定最小

#include <iostream>
#include <cstdio>
#define rep(i,a,b) for (i=a;i<=b;i++)
using namespace std;
int r,c,k;
int b[51][51];
int sx,sy,ex,ey;
int q[2501][2];
int dep[51][51][2];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool judg(int x,int y)
{return x>=1&&x<=r&&y>=1&&y<=c&&b[x][y]==0;
}
bool judge(int x,int y,int z)
{return x>=1&&x<=r&&y>=1&&y<=c&&b[x][y]<=0&&z<dep[x][y][0];
}
void bfs1()
{int h=0,i,j;bool w[51][51];rep(i,1,50) rep(j,1,50) w[i][j]=0;do{h++;rep(i,0,3)if (judg(q[h][0]+dx[i],q[h][1]+dy[i])&&!w[q[h][0]+dx[i]][q[h][1]+dy[i]]){k++;q[k][0]=q[h][0]+dx[i];q[k][1]=q[h][1]+dy[i];w[q[k][0]][q[k][1]]=1;dep[q[k][0]][q[k][1]][0]=dep[q[h][0]][q[h][1]][0]+1;}}while (h<k);
}
void bfs2()
{int h=0,t=1,i,j,state[2501][2];bool w[51][51];rep(i,1,50) rep(j,1,50) w[i][j]=0;state[1][0]=sx;state[1][1]=sy;w[sx][sy]=1;do{h++;rep(i,0,3)if (judge(state[h][0]+dx[i],state[h][1]+dy[i],dep[state[h][0]][state[h][1]][1]+1)&&!w[state[h][0]+dx[i]][state[h][1]+dy[i]]){t++;state[t][0]=state[h][0]+dx[i];state[t][1]=state[h][1]+dy[i];w[state[t][0]][state[t][1]]=1;dep[state[t][0]][state[t][1]][1]=dep[state[h][0]][state[h][1]][1]+1;}}while (h<t);
}
void init()
{int i,j;char p;scanf("%d%d",&r,&c);rep(i,1,r)rep(j,1,c)dep[i][j][0]=2147483647;rep(i,1,r)rep(j,1,c){do{scanf("%c",&p);}while (p!='*'&&p!='.'&&p!='X'&&p!='S'&&p!='D');switch (p){case 'S':{sx=i;sy=j;break;}case 'X':{b[i][j]=1;break;}case '*':{k++;q[k][0]=i;q[k][1]=j;dep[i][j][0]=0;b[i][j]=2;break;}case 'D':{ex=i;ey=j;b[i][j]=-1;break;}default:{break;}}}
}
void doit()
{if (k!=0) bfs1();bfs2();if (dep[ex][ey][1]!=0) printf("%d",dep[ex][ey][1]);else printf("KAKTUS");
}
int main()
{init();doit();
}

这篇关于[BFS]洪水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---