首页 > 其他分享 >水灾 (BFS-先洪水后寻路)

水灾 (BFS-先洪水后寻路)

时间:2022-10-25 12:08:01浏览次数:57  
标签:水灾 node end map int BFS && now 寻路


水灾(sliker)

大雨应经下了几天雨,却还是没有停的样子。ksy刚从外地回来,知道不久除了自己家,其他的地方都将会被洪水淹没。

ksy的老家可以用一个N*M的地图表示,地图上有五种符号:“. * X D S”。其中“X”表示石头,水和人都不能从上面经过。“.”表示平原,ksy和洪水都可以经过。“*”表示洪水开始地方(可能有多个地方开始发生洪水)。“D”表示ksy的家。“S”表示ksy现在的位置。

ksy每分钟可以向相邻位置移动,而洪水将会在ksy移动之后把相邻的没有的土地淹没(从已淹没的土地)。

求ksy回答家最少时间。如他回不了家,被淹死输出KAKTUS。

Input

3 3

D.*

...

.S.

Output

3

Input

3 3

D.*
...

..S

Output

KAKTUS

Input

3 6

D...*.

.X.X..

....S.

Output

6




因为第i秒走后,所到达的点不能有Flood

所以必须在之前Flood,然后再往下找

显然柯黑再同一个地方停留不优

故只要存储到达一个点的最短时间


注意C++中构造函数的写法


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<functional>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN (50+10)

struct node
{
int x,y,t;
node():x(0),y(0),t(0){}
node(int _x,int _y,int _t):x(_x),y(_y),t(_t){/*cout<<x<<' '<<y<<' '<<t<<endl;*/}
}start,end;
/*
node made_node(int i,int j,int t)
{
node now;
now.x=i;
now.y=j;
now.t=t;
return now;
}
*/

int n,m;
bool map[MAXN][MAXN],b[MAXN][MAXN];
char s[MAXN];
queue<node> flood,q;
bool inside(int x,int y)
{
if (x>=1&&x<=n&&y>=1&&y<=m) return true;
return false;
}
bool bfs()
{
int l=-1;
while (!q.empty())
{
node now=q.front();
// cout<<now.x<<' '<<now.y<<endl;
q.pop();
if (now.t>l)
{
int size=flood.size();
while (size)
{
node nowf=flood.front();
flood.pop();
int x=nowf.x,y=nowf.y;
if (x>1&&b[x-1][y])
{
flood.push(node(x-1,y,now.t));
map[x-1][y]=b[x-1][y]=0;
}
if (x<n&&b[x+1][y])
{
flood.push(node(x+1,y,now.t));
map[x+1][y]=b[x+1][y]=0;
}
if (y>1&&b[x][y-1])
{
flood.push(node(x,y-1,now.t));
map[x][y-1]=b[x][y-1]=0;
}
if (y<m&&b[x][y+1])
{
flood.push(node(x,y+1,now.t));
map[x][y+1]=b[x][y+1]=0;
}

size--;
}
l++;
}
int x=now.x,y=now.y;
// if (!map[x][y]) continue;
if (x>1&&map[x-1][y])
{
if (x-1==end.x&&y==end.y){end.t=now.t+1; return true;}
q.push(node(x-1,y,now.t+1));
map[x-1][y]=0;
}
if (x<n&&map[x+1][y])
{
if (x+1==end.x&&y==end.y){end.t=now.t+1; return true;}
q.push(node(x+1,y,now.t+1));
map[x+1][y]=0;
}
if (y>1&&map[x][y-1])
{
if (x==end.x&&y-1==end.y){end.t=now.t+1; return true;}
q.push(node(x,y-1,now.t+1));
map[x][y-1]=0;
}
if (y<m&&map[x][y+1])
{
if (x==end.x&&y+1==end.y){end.t=now.t+1; return true;}
q.push(node(x,y+1,now.t+1));
map[x][y+1]=0;
}





}
return false;
}

int main()
{
freopen("sliker.in","r",stdin);
freopen("sliker.out","w",stdout);
scanf("%d%d",&n,&m);
memset(map,1,sizeof(map));
memset(b,1,sizeof(b));

for (int i=1;i<=n;i++)
{
scanf("%s",s);
for (int j=0;j<m;j++)
{
if (s[j]=='S')
{
start=node(i,j+1,0);
q.push(start);
}
if (s[j]=='D')
{
end=node(i,j+1,0);
b[i][j+1]=0;
}
if (s[j]=='X')
{
map[i][j+1]=0;
b[i][j+1]=0;
}
if (s[j]=='*')
{
map[i][j+1]=0;
b[i][j+1]=0;
flood.push(node(i,j+1,0));
}

}
}
/* for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (map[i][j]) cout<<"map "<<i<<' '<<j<<endl;
cout<<"end"<<end.x<<' '<<end.y;
*/

if (bfs()) printf("%d\n",end.t);
else printf("KAKTUS\n");


// while (1);
return 0;
}



标签:水灾,node,end,map,int,BFS,&&,now,寻路
From: https://blog.51cto.com/u_15724837/5794396

相关文章

  • Nearest Excluded Points ( 转化思想 +多源BFS )
     思路:思路暴力枚举每一个点,暴力做时间会超观察发现:每一个所找的空白点,一定是紧紧挨着红色的点, 于是把这些空白点入队,然后利用bfs,即可搞出来空间用ma......
  • 三维空间的dfs和bfs
    三维空间的dfs和bfs去枚举每一步的6个方向的时候都会用到三个偏移量数组dx[]={1,0,0,-1,0,0};dy[]={0,1,0,0,-1,0};dz[]={0,0,1,0,0,-1};//这样一个for就可以枚举出......
  • 初学bfs
    dfs利用的是栈,bfs利用的是队列如同y总所说的,不需要理解如何用队列实现一个bfs而是跟着y总,告诉我们怎么做,然后我们自己判断一下这种是不是bfs如图:取出的顺序和加入的......
  • bfs + bitmask
    864. ShortestPathtoGetAllKeysYouaregivenan mxn grid grid where:'.' isanemptycell.'#' isawall.'@' isthestartingpoint.Lowercas......
  • 八数码难题——BFS
    原题链接:https://www.acwing.com/problem/content/847/通常情况下很难看出这是一道BFS题或者说看不出怎么表示状态,毕竟它的状态涉及到整个矩阵但是可以用一种unordered_......
  • Snowy Mountain (找规律来贪心+ 多源特殊bfs+根号n)
    题目大意:给定一棵 nn 个点的树,其中每个点可能是黑色或白色。一个点的高度定义为其距离最近黑色节点的距离。你初始在 ii 号节点上,势能为 00,可以做以下两种操作:......
  • A* 自动寻路算法-JavaScript
    效果图代码<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metahttp-equiv="X-UA-Compatible"content="IE=edge"><metaname="viewport"......
  • 基于全志D1-H哪吒的 自动寻路小车-附源码
    本文内容为【玄铁杯第二届RISC-V应用创新大赛】作业作者:智航追迹队原文链接:https://occ.t-head.cn/community/post/detail?spm=a2cl5.14300636.0.0.429d180fr0b8Om&id=409......
  • UESTC 482 Charitable Exchange(优先队列+bfs)
    CharitableExchangeTimeLimit:4000/2000MS(Java/Others)   MemoryLimit:65535/65535KB(Java/Others)Submit StatusHaveyoueverheardastarcharityshow......
  • HDU 1885 Key Task(BFS)
    KeyTaskTimeLimit:3000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1809    AcceptedSubmission(s):770Pr......