[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。

相关文章

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，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎，细嗅蔷薇。你好朋友，这里是锅巴的C\C++学习笔记，常言道，不积跬步无以至千里，希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目： 牛牛发明了一种新的四舍五入应用于整数，对个位四舍五入，规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数
阅读更多...
深度优先（DFS）和广度优先（BFS）——算法

深度优先（DFS）和广度优先（BFS）——算法

深度优先 深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访
阅读更多...
【算法专场】模拟（下）

【算法专场】模拟（下）

目录 前言 38. 外观数列 算法分析 算法思路 算法代码 1419. 数青蛙 算法分析 算法思路 算法代码  2671. 频率跟踪器 算法分析 算法思路 算法代码 前言 在前面我们已经讲解了什么是模拟算法，这篇主要是讲解在leetcode上遇到的一些模拟题目~ 38. 外观数列 算法分析 这道题其实就是要将连续且相同的字符替换成字符重复的次数+
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2