本文共 1783 字，大约阅读时间需要 5 分钟。
链接：https://ac.nowcoder.com/acm/contest/7872/M
来源：牛客网众所周知，浙农林是一条河。由于浙江农林大学的特殊地形，当你在下雨后漫步在农林大路上的时候难免会出现一脚踩进一个水坑的情况的情况。而农农非常不喜欢踩到水坑的感觉，请你帮忙设计一个程序来帮助农农判断他能否在不踩入水坑的情况下回到寝室。已知，浙江农林大学可以表示为一个 N * N 的矩阵。对于每个位置有一个海拔数据 h[i][j]，当水位高度大于 h[i][j] 的时候，这个位置就会形成一个水坑。农农现在的坐标是 (1, 1), 他的宿舍位于 (n， n).农农只可以沿着上下左右四个方向走。假如农农现在位于 （2， 2）那么在不考虑水位的情况下，他可以去的地方有
（1， 2），（2，1）， （3， 2） ，（2， 3）
N （表示矩阵大小）接下来 N 行为一个 N * N 的矩阵 hQ （表示询问数量）接下来 Q 行每行一个数字，表示当前水位 X 1 <= N <= 10001 <= h[i][j] <= 1000001 <= X <= 1000001 <= Q <= 100000
共 Q 行，表示在对应水位下，农农能否在不踩入水坑的情况下回到寝室, 如果农农可以回到寝室，请你输出“Wuhu”， 反之请输出“Hmmm”
输入
4 5 2 3 2 4 5 3 4 2 1 4 5 3 3 3 3 2 1 5 输出 Wuhu Hmmm对于第一次询问，没有任何一个位置形成水坑，所以农农可以从（1， 1）走到（4， 4）
对于第二次询问 高度小于 5 的位置形成了水坑，其中包括目的地 （4， 4）所以农农无法在 不踩到水坑的情况下走到（4， 4）可以用二分求出最大可到达宿舍的水位高度x，如果当前水位小于等于x，可以回到宿舍，大于x，不能回到宿舍。用bfs来判断水位高度是否合适。
#include#define ll long longusing namespace std;const int N =1e3+10;int a[N][N],n;int vis[N][N];int dx[4]={ 1,-1,0,0};int dy[4]={ 0,0,1,-1}; struct node{ int x,y;};int check(int t){ memset(vis,0,sizeof(vis)); if(t>a[1][1]) return 0; queue q; node u,v; u.x=1,u.y=1; q.push(u); vis[1][1]=1; while(!q.empty()) { u=q.front(); q.pop(); if(u.x==n&&u.y==n) return 1; for(int i=0;i<4;i++) { int xx=u.x+dx[i]; int yy=u.y+dy[i]; if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&vis[xx][yy]==0&&a[xx][yy]>=t) { v.x=xx,v.y=yy; vis[xx][yy]=1; q.push(v); } } } return 0;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&a[i][j]); } } int l=1,r=100000; int t; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) l=mid+1,t=mid; else r=mid-1; } int q; scanf("%d",&q); while(q--) { int x; scanf("%d",&x); if(x<=t) printf("Wuhu\n"); else printf("Hmmm\n"); } return 0;}
转载地址：http://hpzgz.baihongyu.com/