题目大意：找出一条第一行到路径第n行，使得路径上的最大值最小，输出这个值
最大值最小，不就是二分答案的标志吗？我们二分路径上的最大值，转为判定。
然后跑一遍BFS，若下个格子的值小于等于mid则可以走，否则不行，走到了第n行就return 1
我才不会告诉你我第一时间想的是二分答案+最短路
#include<iostream> #include<iomanip> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> using namespace std; #define INF 0x7fffffff inline int read() { char ch; bool bj=0; while(!isdigit(ch=getchar())) bj|=(ch=='-'); int res=ch^(3<<4); while(isdigit(ch=getchar())) res=(res<<1)+(res<<3)+(ch^(3<<4)); return bj?-res:res; } void printnum(int x) { if(x>9)printnum(x/10); putchar(x%10+'0'); } inline void print(int x,char ch) { if(x<0) { putchar('-'); x=-x; } printnum(x); putchar(ch); } int n,m,a[1005][1005],cnt,maxn; int ans; queue<pair<int,int> >q; int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; bool vst[1005][1005]; inline bool BFS(int limit){ while(!q.empty())q.pop(); memset(vst,0,sizeof(vst)); q.push(make_pair(1,1)); vst[1][1]=1; while(!q.empty()){ int x=q.front().first,y=q.front().second; for(int i=0;i<4;i++){ int tx=x+dx[i],ty=y+dy[i]; if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]<=limit&&!vst[tx][ty]){ vst[tx][ty]=1; if(tx==n)return 1; q.push(make_pair(tx,ty)); } } q.pop(); } return 0; } signed main() { n=read(); m=read(); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){ a[i][j]=read(); maxn=max(maxn,a[i][j]); } int l=0,r=maxn; while(l<=r) { int mid=(l+r)>>1; if(BFS(mid)) { ans=mid; r=mid-1; } else l=mid+1; } print(ans,' '); return 0; }