二分加bfs50分求调

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;

const int N = 1010;

int g[N][N];
int n,m;
PII f[N*N];
int tt = -1, hh;
bool st[N][N];
bool check(int mid)
{
    memset(st,false,sizeof st);
    tt = - 1, hh = 0;
    f[++ tt] = {1,1};
    int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
    while(hh <= tt)
    {
        auto t = f[hh ++];
        if(t.first == n)return true;
        if(!st[t.first][t.second])
        {
            for(int i = 0; i < 4; i ++)
            {
                if(t.first + dx[i] >= 1 && t.second + dy[i] >= 1 && t.first + dx[i] <= n && t.second + dy[i] <= m && g[t.first + dx[i]][t.second + dy[i]] <= mid)
                {
                    f[++ tt] = {t.first + dx[i], t.second + dy[i]};
                }
            }
        }
        st[t.first][t.second] = true;
    }
    return false;
}


int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            scanf("%d",&g[i][j]);
    int l = 0, r = 1000;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid))r = mid;
        else l = mid + 1;
    }
    cout << l;
}