https://ac.nowcoder.com/acm/contest/318/F

C++版本一

题解：思路：二分+搜索，每次二分利姆鲁的初始攻击值，如果这个攻击值能够拯救到静就将mid赋值给ub，同时令ans = mid，否则就将mid赋值给lb，最后输出ans即可。

#include<bits/stdc++.h>
using namespace std;

int t, n, sx, sy, ex, ey;
int mp[505][505], vis[505][505];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

struct node {
    int x, y;
}nw, nxt;

bool go(int x, int y) {
    if(x < 1 || x > n) return false;
    if(y < 1 || y > n) return false;
    if(vis[x][y]) return false;
    return true;
}

bool check(int x) {
    queue<node> q;
    memset(vis, 0, sizeof(vis));
    nw.x = sx, nw.y = sy;
    vis[sx][sy] = 1;
    q.push(nw);
    while(!q.empty()) {
        nw = q.front(); q.pop();
        if(nw.x == ex && nw.y == ey) return true;
        for(int i  = 0; i < 4; i++) {
            nxt.x = nw.x + dx[i];
            nxt.y = nw.y + dy[i];
            if(go(nxt.x, nxt.y) && mp[nxt.x][nxt.y] <= x) {
                q.push(nxt);
                vis[nxt.x][nxt.y] = 1;
            }
        }
    }
    return false;
}

int main() {
    scanf("%d", &t);
    while(t--) {
        int mx = -1;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                scanf("%d", &mp[i][j]);
                mx = max(mx, mp[i][j]);
            }
        }
        scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
        int ub = mx, lb = 0, mid;
        while(ub >= lb) {
            mid = (ub + lb) >> 1;
            if(check(mid)) {
                ub = mid - 1;
            } else {
                lb = mid + 1;
            }
        }
        printf("%d\n", lb);
    }
    return 0;    
}

C++版本二

题解：

二分+BFS

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k;
int a[N][N];
int b[][2]={1,0,0,1,-1,0,0,-1};
int vis[N][N];
int sx,sy,ex,ey;
struct node{
    int x,y;
}f,s,tmp;
bool bfs(int x){
    memset(vis,0,sizeof(vis));
    queue<node>q;
    s.x=sx;
    s.y=sy;
    vis[sx][sy]=1;
    q.push(s);
    while(!q.empty()){
        f=q.front();
        q.pop();

        if(f.x==ex&&f.y==ey){
            return 1;
        }
        for(int i=0;i<4;i++){
            tmp.x=f.x+b[i][0];
            tmp.y=f.y+b[i][1];//cout<<tmp.x<<" "<<tmp.y<<endl;
            if(1<=tmp.x&&tmp.x<=n&&1<=tmp.y&&tmp.y<=n&&!vis[tmp.x][tmp.y]&&x>=a[tmp.x][tmp.y]){
                vis[tmp.x][tmp.y]=1;
                q.push(tmp);
            }
        }
    }
    return 0;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    while(~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);
            int l=0;
            int r=1e5;
            int mid;
            int ans=0;
            while(l<=r){
                mid=(l+r)>>1;
                if(bfs(mid)){
                    ans=mid;
                    r=mid-1;
                }else{
                    l=mid+1;
                }
            }
            printf("%d\n",ans);

        }
    }


    //cout << "Hello world!" << endl;
    return 0;
}