M-灾难预警-浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛

题目：灾难预警

众所周知，浙农林是一条河。
由于浙江农林大学的特殊地形，当你在下雨后漫步在农林大路上的时候
难免会出现一脚踩进一个水坑的情况的情况。而农农非常不喜欢踩到水坑的感觉，
请你帮忙设计一个程序来帮助农农判断他能否在不踩入水坑的情况下回到
寝室。
已知，浙江农林大学可以表示为一个 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