题干：
有一天，利姆鲁在这个世界最重要的人静被魔王带走，并将其困在一个n*n的迷宫内的某一处，迷宫的每个格子都可能有一只魔物，魔物的攻击力为a[i][j]，因而利姆鲁只有当攻击力大于等于a[i][j]才能通过这个方格，否则就只能绕道（只能朝上下左右四个方向）而行。
为了拯救静，利姆鲁决定勇闯迷宫！
现在利姆鲁站在（sx，sy）处，静在（ex，ey）处，为了保证自己能够成功拯救静，利姆鲁在初始时靠捕食者将自己的攻击力提升到x后才出发，但是由于时间紧急（利姆鲁不想和静分开太久），使用捕食者需要花费时间，所以利姆鲁想知道能够成功救出静的最小的x（默认初始位置的魔物对利姆鲁无攻击，即此位置对其而言是安全位置）是多少。
输入描述:
第一行为一个正整数t（1<=t<=20)，表示测试数据的数量。每组数据第一行为一个正整数n（1<=n<=500)，表示迷宫大小。第2行至第n+1行，每行有n个整数，相邻两个数用空格隔开。第i行第j列的数a[i][j]表示这一个方格中的魔物的攻击力大小为a[i][j]（0<=a[i][j]<=1e5)。第n+2行为四个正整数sx，sy，ex，ey（相邻两个数用空格隔开），分别表示利姆鲁的坐标和静的坐标。(1<=sx，sy，ex，ey<=n)。
输出描述:
利姆鲁初始的攻击力的最小值x（大于等于0的整数）。
示例1
输入
复制
151 2 3 4 51 2 3 4 73 4 2 1 37 8 1 2 33 1 2 3 61 1 5 5
输出
复制
6
说明
其中一条使得初始攻击力最小的路线为(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)->(5,5)，此时初始攻击力只要6，因而答案是6。
解题报告：
二分一下需要提升的攻击力，然后搜索check是否可以满足就可以了。
AC代码：
#include<cstdio>#include<iostream>#include<algorithm>#include<queue>#include<map>#include<vector>#include<set>#include<string>#include<cmath>#include<cstring>#define ll long long#define pb push_back#define pm make_pair#define fi first#define se secondusing namespace std;const int MAX = 2e5 + 5;int n;int sx,sy,ex,ey;int mid;bool flag;int a[555][555];bool vis[555][555];int nx[4] = {0,1,0,-1};int ny[4] = {1,0,-1,0};bool ok(int x,int y) {if(x>=1 && x<=n && y>=1 && y<=n) return 1;else return 0;}void dfs(int x,int y) {if(x == ex && y == ey) {flag = 1;return;}for(int k = 0; k<4; k++) {int tx = x + nx[k];int ty = y + ny[k];if(ok(tx,ty) == 0) continue;if(a[tx][ty] > mid) continue;if(vis[tx][ty]) continue;vis[tx][ty] = 1;dfs(tx,ty);if(flag) return;}}int main(){int t;cin>>t;while(t--) {scanf("%d",&n);int maxx = 0;for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) {scanf("%d",&a[i][j]);maxx = max(maxx,a[i][j]);}}scanf("%d%d%d%d",&sx,&sy,&ex,&ey);int l = a[ex][ey],r = maxx;mid = (l+r)>>1;int ans = 0;/如果不加=0？ while(l<=r) {mid = (l+r)>>1;memset(vis,0,sizeof vis);vis[sx][sy] = 1;flag = 0;dfs(sx,sy);if(flag) r = mid-1, ans = mid;else l = mid+1;}printf("%d\n",ans);}return 0 ;}
不加=0也可以AC，，说明数据保证有解了。
这题也可以用类似并查集的东西，就是先把二维坐标变成线性的，然后并查集：把值为a[i][j]的push_back到对应的vector中，然后从小到大枚举答案一直到起点和终点被并到同一个集合中，结束程序。
#include<cstdio>#include<iostream>#include<algorithm>#include<queue>#include<map>#include<vector>#include<set>#include<string>#include<cmath>#include<cstring>#define ll long long#define pb push_back#define pm make_pair#define fi first#define se second#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)#define REP(I, N) for (int I = 0; I < (N); ++I)using namespace std;const int SIZE = 1e5+10;typedef pair<int,int> PII;typedef vector<int> VI;typedef vector<ll> VL;typedef vector<PII> VPII;struct Union_Find {int d[250001],num[250001];void init(int n) {REP(i,n)d[i]=i,num[i]=1;}int find(int x) {return (x!=d[x])?(d[x]=find(d[x])):x;}bool is_root(int x) {return d[x]==x;}bool uu(int x,int y) {x=find(x);y=find(y);if(x==y)return 0;if(num[x]>num[y])swap(x,y);num[y]+=num[x];d[x]=y;return 1;}} U;VPII pp[SIZE];int a[555][555];int dx[4]= {1,0,-1,0};int dy[4]= {0,1,0,-1};int main() {CASET {int n;cin>>n;U.init(n*n);REP(i,SIZE)pp[i].clear();REP(i,n)REP(j,n) {scanf("%d",&a[i][j]);pp[a[i][j]].pb({i,j});}PII st,ed;scanf("%d%d",&st.fi,&st.se);scanf("%d%d",&ed.fi,&ed.se);st.fi--;st.se--;ed.fi--;ed.se--;a[st.fi][st.se]=0;pp[0].pb(st);REP(i,SIZE) {for(auto p:pp[i]) {REP(j,4) {int nx=p.fi+dx[j];int ny=p.se+dy[j];if(nx<0||ny<0||nx>=n||ny>=n)continue;if(a[nx][ny]<=i)U.uu(p.fi*n+p.se,nx*n+ny);}}if(U.find(st.fi*n+st.se)==U.find(ed.fi*n+ed.se)) {printf("%d\n",i);break;}}}return 0;}
还有一种方法：
优先队列维护权值小根堆，然后bfs整张地图一次，同时权值递增的同时维护最大值，也就是如果一条路是1->3->2，那整2那个地方的权值也是3。大概是这个意思。
#include<bits/stdc++.h>using namespace std;const int N=505;struct node{int x,y,g;bool friend operator<(node c,node d){return c.g>d.g;}}no,ne;int a[N][N],n,sx,sy,ex,ey,m[4][2]={1,0,-1,0,0,1,0,-1};bool vis[N][N];void bfs(){memset(vis,0,sizeof(vis));priority_queue<node>q;no.x=sx;no.y=sy;no.g=0;vis[no.x][no.y]=1;q.push(no);while(!q.empty()){no=q.top();q.pop();if(no.x==ex&&no.y==ey){printf("%d\n",no.g);return;}for(int i=0;i<4;i++){ne.x=no.x+m[i][0];ne.y=no.y+m[i][1];if(ne.x<1||ne.x>n||ne.y<1||ne.y>n||vis[ne.x][ne.y])continue;ne.g=max(no.g,a[ne.x][ne.y]);vis[ne.x][ne.y]=1;q.push(ne);}}}int main(){int T;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);scanf("%d%d%d%d",&sx,&sy,&ex,&ey);bfs();}}
