[noip模拟]水灾BFS

2023-10-30 06:59
文章标签 模拟 bfs noip 水灾

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

水灾（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!!!”。

输入文件 sliker.in

输出文件 sliker.out

Input

3 3

D.*

…

.S.

 

Output

3

 

Input

3 3

D.*
…

..S

 

Output

ORZ hzwer!!!

 

Input

3 6

D...*.

.X.X..

....S.

 

Output

6

-----------------------------------------------------------------------------------------------------------------------------------------

其实我相信所有人看见这道题都会想到BFS，而且会觉得很简单，我也不例外，但是我竟然还是错了5组数据，四组崩溃，一组WA，我一开始是以为我的BFS写挂了致使空间爆了

在加上之前的几道BFS都挂了，所以我一度对自己的BFS失去信心，直到现在才发现这道题错了纯属自己犯二。。。。。

这道题的思路很好想的，就是跑个BFS，只是有一点与正常BFS有些出入，就是在每一层运行时，要把所有时间点相同（即是要同一时刻的水和人遍历完后才运行下一层）

然后还要一点就是要先跑洪水再走人，因为如果人先走了，但是同时水也淹没了这个位置，那这个位置就是不能去的，但是先走人会把这个点标记成有人（当然这个可以后期处理，不过先水再人可以更好的理解，推荐用这种）

 

然后还有一个 小细节就是要对存水的队列判空，要不为空的时候才继续让水蔓延，否则会崩溃（如果存水的队列在为空时没有跳出，就会让程序崩溃，感兴趣的可以试试QAQ）

 

好了接下来就是发这个让我崩溃很久的水题的代码

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<cstdlib>
  7 #include<queue>
  8 #include<ctime>
  9 #define maxn 70
 10 using namespace std;
 11 
 12 const int dx[]={-1,1,0,0};
 13 const int dy[]={0,0,-1,1};
 14 
 15 struct node{
 16     int x,y,cnt;
 17 };
 18 
 19 queue<node>flood;
 20 queue<node>ccy;
 21 
 22 int n,m,map[maxn][maxn],tot;
 23 int sx,sy,fx,fy,real;
 24 
 25 int back()
 26 {
 27     for(int i=0;i<4;i++)
 28     {
 29         int ox=fx+dx[i],oy=fy+dy[i];
 30         if(ox<1||ox>n||oy<1||oy>m)continue;
 31         if(map[ox][oy]==0||map[ox][oy]==2)return false;//可以回家 
 32     }
 33     return true;
 34 }
 35 
 36 void people()
 37 {
 38         int zx=0,zy=0;
 39         node f=ccy.front();
 40         int tt=f.cnt;
 41         while(tt==f.cnt){
 42             f=ccy.front();        
 43             ccy.pop();
 44             for(int i=0;i<4;i++)
 45             {
 46                 zx=f.x+dx[i];zy=f.y+dy[i];
 47                 if(map[zx][zy]==1||map[zx][zy]==-1||map[zx][zy]==2)continue;
 48                 if(zx<1||zx>n||zy<1||zy>m)continue;
 49                 map[zx][zy]=2;
 50                 ccy.push((node){zx,zy,f.cnt+1});
 51                 if(zx==fx&&zy==fy)
 52                 {
 53                     printf("%d ",f.cnt+1);real=1;return;
 54                 }
 55             }
 56             f=ccy.front();
 57         }
 58 }
 59 
 60 void water()
 61 {
 62         int zx=0,zy=0;
 63         if(!flood.empty())
 64         {
 65             node e=flood.front();
 66             int cn=e.cnt;
 67             while(e.cnt==cn)
 68             {    
 69                 e=flood.front();
 70                 flood.pop();
 71                 for(int i=0;i<4;i++)
 72                 {
 73                     zx=e.x+dx[i];zy=e.y+dy[i];
 74                     if(map[zx][zy]==-1||map[zx][zy]==1)continue;
 75                     if(zx<1||zx>n||zy<1||zy>m)continue;
 76                     if(zx==fx&&zy==fy)continue;
 77                     map[zx][zy]=1;
 78                     flood.push((node){zx,zy,e.cnt+1});
 79                 }
 80                 e=flood.front();
 81             }
 82         }
 83 }
 84 
 85 void read(){
 86     scanf("%d%d",&n,&m);
 87     for(int i=1;i<=n;i++)
 88     {
 89         char c[55];
 90         scanf("%s",c);
 91         for(int j=0;j<m;j++)
 92         {
 93             if(c[j]=='X')
 94             map[i][j+1]=-1;
 95             if(c[j]=='S')
 96             {sx=i,sy=j+1;ccy.push((node){i,j+1,0});}
 97             if(c[j]=='D')
 98             fx=i,fy=j+1;
 99             if(c[j]=='*')
100             map[i][j+1]=1,flood.push((node){i,j+1,0});
101         }
102     }
103 }
104 
105 int main()
106 {
107     freopen("sliker.in","r",stdin);
108     freopen("sliker.out","w",stdout);
109     read();
110     map[sx][sy]=2;
111     while(!ccy.empty()&&!back())
112     {
113         water();
114         people();
115         if(real==1)return 0;
116     }
117     printf("ORZ hzwer!!!");//注意细节 
118 }
View Code

 

 

 

 

-------------分界线QWQ--------------接下来我再提供几组数据

1.in

10 10
D..........
...........
...........
...........
...........
...........
........S..
...........
...........
...........

1.out

14

 

2.in

10 15
........X......
..XXXXX.X.*....
X.....X.X..*...
.X.S..X.X......
D.X...X.XXXXX..
.X....X........
.X....X.XXXXXXX
.XXXXXX.X......
........X......
XXXXXXXXX...*..

2.out

ORZ hzwer!!!

 

3.in

50 50
D.................................................
.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.XX.............................................X.
...*............................................X.
.XX.............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
.X..............................................X.
SXXXXXXXXXXXXXXXXXXXXXXXX.X.XXXXXXXXXXXXXXXXXXXXX.
..........................X.......................

3.out

152

转载于:https://www.cnblogs.com/Danzel-Aria233/p/7482190.html

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


http://www.chinasem.cn/article/306330。

相关文章

Python使用pynput模拟实现键盘自动输入工具

Python使用pynput模拟实现键盘自动输入工具

《Python使用pynput模拟实现键盘自动输入工具》在日常办公和软件开发中,我们经常需要处理大量重复的文本输入工作,所以本文就来和大家介绍一款使用Python的PyQt5库结合pynput键盘控制... 目录概述：当自动化遇上可视化功能全景图核心功能矩阵技术栈深度效果展示使用教程四步操作指南核心代码解析
阅读更多...
Python模拟串口通信的示例详解

Python模拟串口通信的示例详解

《Python模拟串口通信的示例详解》pySerial是Python中用于操作串口的第三方模块,它支持Windows、Linux、OSX、BSD等多个平台,下面我们就来看看Python如何使用pySe... 目录1.win 下载虚www.chinasem.cn拟串口2、确定串口号3、配置串口4、串口通信示例5
阅读更多...
CSS模拟 html 的 title 属性(鼠标悬浮显示提示文字效果)

CSS模拟 html 的 title 属性(鼠标悬浮显示提示文字效果)

《CSS模拟html的title属性(鼠标悬浮显示提示文字效果)》：本文主要介绍了如何使用CSS模拟HTML的title属性，通过鼠标悬浮显示提示文字效果，通过设置`.tipBox`和`.tipBox.tipContent`的样式，实现了提示内容的隐藏和显示，详细内容请阅读本文，希望能对你有所帮助... 效
阅读更多...
hdu1254（嵌套bfs，两次bfs）

hdu1254（嵌套bfs，两次bfs）

/*第一次做这种题感觉很有压力，思路还是有点混乱，总是wa，改了好多次才ac的思路：把箱子的移动当做第一层bfs，队列节点要用到当前箱子坐标（x，y），走的次数step，当前人的weizhi（man_x，man_y），要判断人能否将箱子推到某点时要嵌套第二层bfs（人的移动）；代码如下：
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
usaco 1.2 Transformations（模拟）

usaco 1.2 Transformations（模拟）

我的做法就是一个一个情况枚举出来 注意计算公式： （ 变换后的矩阵记为C） 顺时针旋转90°：C[i] [j]=A[n-j-1] [i] （旋转180°和270° 可以多转几个九十度来推） 对称：C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<
阅读更多...
poj 2195 bfs+有流量限制的最小费用流

poj 2195 bfs+有流量限制的最小费用流

题意： 给一张n * m（100 * 100）的图，图中” . " 代表空地， “ M ” 代表人， “ H ” 代表家。 现在，要你安排每个人从他所在的地方移动到家里，每移动一格的消耗是1，求最小的消耗。 人可以移动到家的那一格但是不进去。 解析： 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了，先抽象出源点s和汇点t。 令源点与每个人相连，容量为1，费用为
阅读更多...
hdu4431麻将模拟

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况： 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想： 对于某张牌>=3个，先减去3个相同，再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti
阅读更多...
POJ 3057 最大二分匹配+bfs + 二分

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2