洪水

2024-01-29 19:48
文章标签 洪水

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

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;
}

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



http://www.chinasem.cn/article/657998

相关文章

算法【洪水填充】

洪水填充是一种很简单的技巧,设置路径信息进行剪枝和统计,类似感染的过程。路径信息不撤销,来保证每一片的感染过程可以得到区分。看似是暴力递归过程,其实时间复杂度非常好,遍历次数和样本数量的规模一致。 下面通过一些题目来加深理解。 题目一 测试链接:https://leetcode.cn/problems/number-of-islands/ 分析:洪水填充更可以看作是一个感染过程,将空间

使用 Scapy 库编写 TCP ACK 洪水攻击脚本

一、介绍 TCP ACK洪水攻击是一种分布式拒绝服务攻击(DDoS),攻击者通过向目标服务器发送大量伪造的TCP ACK(确认)数据包,使目标服务器不堪重负,无法正常处理合法请求。虽然ACK包通常用于确认接收到的数据,但在这种攻击中,ACK包被用作耗尽目标系统资源的工具。 1.2 工作原理 大量伪造的ACK包:攻击者生成大量伪造的TCP ACK包,通常会随机伪造源IP地址,使追踪攻击源变得困

积鼎CFDPro水文水动力模型,专为中小流域洪水“四预”研发的流体仿真技术

水动力模型与水文模型是水利工程与水文学研究中不可或缺的两大工具。水动力模型着重于流体运动的动力学机制,通过一系列方程组捕捉水流的时空变化,而概念性水文模型则侧重于流域尺度的水文循环过程,利用物理概念与经验关系进行近似模拟。两者相互补充,共同构成了现代水文学与水资源管理领域的核心分析手段。积鼎科技结合了水文的产流机制和水动力的对流动的准确计算,创新研发CFDpro—水文水动力模型,这是一种充分适用于

TLS洪水攻击是什么,如何进行有效的防护

今天,我们将深入研究一种典型的DDOS攻击类型——TLS洪水攻击,TLS(传输层安全)洪水攻击可以淹没大多数DDoS防护解决方案。因此如果您使用了错误的解决方案,意味着您的Web应用程序面临很大的风险! 传输层安全性协议(英语:Transport Layer Security,缩写作TLS),及其前身安全套接层(Secure Sockets Layer,缩写作SSL)是一种安全协议,目的是为互联

GEE案例——广东省梅州市梅县区松口镇的梅江横山水灾监测(利用sentinel-1和大津法计算洪水时序面积)

背景 2024年4月5日晚,广东省气象部门发布消息称,4月5日0时到20时,广东中北部出现了暴雨到大暴雨,其中从化吕田累计雨量最大达到225.7毫米。累计降水量达到大暴雨的地方还包括惠州龙门县永汉镇205.2毫米、清远佛冈县水头镇188.6毫米、韶关新丰县梅坑镇174.5毫米、河源东源县新回龙镇166.1毫米。 2024年4月7日13时19分起,据市气象台监测,广州市达到启动气象灾害(暴雨)Ⅲ

【Kaggle】练习赛《洪水数据集的回归预测》(上)

前言 关于 kaggle 月赛也不多说明,前面两篇《肥胖风险的多类别预测》和 《鲍鱼年龄预测》 已做详细说明。分别是一个分类模型和一个回归模型。本期是2024年5月份的题目《Regression with a Flood Prediction Dataset 》即《洪水数据集的回归预测》,本以为回归模型,与前一篇差不多,没有什么新意,也想写有没有写这篇文章的必要。可随着参与这竞赛后,发现与我之前

FloodFill-----洪水灌溉算法(DFS例题详解)

目录 一.图像渲染: 代码详解: 二.岛屿数量: 代码详解: 三.岛屿的最大面积: 代码详解: 四.被围绕的区域: 代码详解: 五.太平洋大西洋水流问题: 代码详解: FloodFill算法简介:FloodFill(泛洪填充)算法是一种图像处理的基本算法,用于填充连通区域。该算法通常从一个种子点开始,沿着种子点的相邻像素进行填充,直到遇到边界或者其他指定的条件为止。F

网易2020届笔试题--洪水高度把通信基站淹没后会分为几组?

比如10个基站的高度依次是12,13,34,9,15,11,9,18,20,22,如下是3个洪水高度: 如果洪水高度是1,那么会分为1组(12,13,34,9,15,11,9,18,20,22) 如果洪水高度是10,那么会分为3组(12,13和34,15,11和18,20,22) 如果洪水高度是11,那么会分为3组(12,13,34和15和18,20,22) 输入: 10 12 13

BZOJ 4712 洪水

Description 小A走到一个山脚下,准备给自己造一个小屋。这时候,小A的朋友(op,又叫管理员)打开了创造模式,然后飞到山顶放了格水。于是小A面前出现了一个瀑布。作为平民的小A只好老实巴交地爬山堵水。那么问题来了:我们把这个瀑布看成是一个n个节点的树,每个节点有权值(爬上去的代价)。小A要选择一些节点,以其权值和作为代价将这些点删除(堵上),使得根节点与所有叶子结点不连通。问最小代价。不

记内网http洪水攻击,导致网页无法访问一事

事由 最近两日,部分同事在访问税纪云平台时,登录跳转页面频繁转圈、要么就是出现无法连接的错误提示。 无法访问此页面已重置连接。请尝试:·检查连接· 检查代理和防火墙· 运行 Windows 网络诊断 经过以下几方面的排查,无果。 后续通过检查防火墙的日志,发现有问题的客户端多数存在tcp丢包情况发生并提示==Https flood attack==http洪水攻击。