题干：
有一天，利姆鲁在这个世界最重要的人静被魔王带走，并将其困在一个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
输入
1
5
1 2 3 4 5
1 2 3 4 7
3 4 2 1 3
7 8 1 2 3
3 1 2 3 6
1 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 second
using 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();
}
}
京公网安备 11010502036488号