M-灾难预警-浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛
程序员文章站
2022-06-25 16:10:22
题目:灾难预警众所周知,浙农林是一条河。由于浙江农林大学的特殊地形,当你在下雨后漫步在农林大路上的时候难免会出现一脚踩进一个水坑的情况的情况。而农农非常不喜欢踩到水坑的感觉,请你帮忙设计一个程序来帮助农农判断他能否在不踩入水坑的情况下回到寝室。已知,浙江农林大学可以表示为一个 N * N 的矩阵。对于每个位置有一个海拔数据 h[i][j],当水位高度大于 h[i][j] 的时候,这个位置就会形成一个水坑。农农现在的坐标是 (1, 1), 他的宿舍位于 (n, n).农农只可以沿着上下左右...
题目:灾难预警
众所周知,浙农林是一条河。
由于浙江农林大学的特殊地形,当你在下雨后漫步在农林大路上的时候
难免会出现一脚踩进一个水坑的情况的情况。而农农非常不喜欢踩到水坑的感觉,
请你帮忙设计一个程序来帮助农农判断他能否在不踩入水坑的情况下回到
寝室。
已知,浙江农林大学可以表示为一个 N * N 的矩阵。
对于每个位置有一个海拔数据 h[i][j],当水位高度大于 h[i][j] 的时候,
这个位置就会形成一个水坑。
农农现在的坐标是 (1, 1), 他的宿舍位于 (n, n).
农农只可以沿着上下左右四个方向走。
假如农农现在位于 (2, 2)那么在不考虑水位的情况下,他可以去的地方有
(1, 2),(2,1),(3, 2),(2, 3)
输入描述:
输出描述:
样例:
思路:这题一道简单的bfs+优先队列,按层次遍历,将遍历到的点存入队列,然后不断取出h大的节点,继续遍历,当遍历到n,n,时结束,以遍历过程中的最小h为依据,水位<=h,能走,否则,不能。有点贪心的味道。
#include<bits/stdc++.h>
using namespace std;
int mapp[1005][1005];
int minn=10000000;
int dis[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int us[1005][1005]={0};
int flag=0;
int n;
struct s{
int x;
int y;
int z;
};
bool operator<(s a , s b){
return a.z<b.z;
}
priority_queue<s>q;
void bfs(int a,int b,int c){
q.push({a,b,c});
while(!q.empty()){
int t=q.top().z;
int l=q.top().x;
int r=q.top().y;
q.pop();
if(l==n&&r==n){
flag=t;
return;
}
for(int i=0;i<4;i++){
int x=l+dis[i][0];
int y=r+dis[i][1];
if(x>0&&y>0&&x<=n&&y<=n&&us[x][y]==0){
us[x][y]=1;
if(mapp[x][y]<t)
q.push({x,y,mapp[x][y]});
else
q.push({x,y,t});
}
}
}
}
int main(){
cin>>n;
for(int j=1;j<=n;j++){
for(int l=1;l<=n;l++){
scanf("%d",&mapp[j][l]);
}
}
us[1][1]=1;
bfs(1,1,mapp[1][1]);
int q;
scanf("%d",&q);
for(int j=1;j<=q;j++){
int p;
scanf("%d",&p);
if(p>flag){
printf("Hmmm\n");
}
else
printf("Wuhu\n");
}
}
本文地址:https://blog.csdn.net/MarilynYangYang/article/details/109265964
上一篇: 账号分享ios《Lanota》
下一篇: 【ZZULIOJ】1029: 三角形判定
推荐阅读
-
浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛-D 涛涛和策策的游戏(尼姆博弈)
-
浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛部分题题解
-
M-灾难预警-浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛
-
浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛(同步赛)训练记录
-
每日咕咚(C++)---浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛(同步赛)
-
浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛(同步赛)训练记录
-
M-灾难预警-浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛
-
浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛-D 涛涛和策策的游戏(尼姆博弈)
-
浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛——F 学长的白日梦
-
浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛——I 来解方程吧