Luogu p1902 assassinating Ambassador (two points | BFS)

Title Description

Ideas

Dichotomy adopt BFS Go through the answers

Code 1

#include <iostream>
#include <queue>
#include <utility>//pair
#include <cstring>
using namespace std; 
typedef pair<int ,int> PII;
const int N = 1010;
int n, m, l = N, r = - N, mid, ans;
int p[N][N];
bool st[N][N];// It means have you ever been here   prune ！
int dx[4] = {
    1, 0, -1, 0}, dy[4] = {
    0, 1, 0, -1};

bool cheak(int x, int y, int maxn) {
    //BFS
    queue<PII> q;
    q.push({
    x, y});
    st[x][y] = true;
    while(!q.empty()) {
    
        auto t = q.front();
        q.pop();
        for(int i = 0; i < 4; i ++) {
    
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x < 1 || x > n || y < 1 || y > m || st[x][y] || p[x][y] > maxn) {
    
                continue;
            }
            st[x][y] = true;
            if(x == n) {
     // If you can go to the n That's ok 
                return true;
            } else {
    
                q.push({
    x, y});
            }
        }
    }
    return false;
}

int main () {
    
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) {
    
        for (int j = 1; j <= m; j ++) {
    
            cin >> p[i][j];
            r = max(r, p[i][j]);
            l = min(l, p[i][j]);
        }
    }
    while(l < r) {
    // Find the left boundary 
        mid = (l + r) >> 1;
        memset(st , false, sizeof st);
        if(cheak(1, 1, mid)) {
    
            r = mid;
            ans = mid;
        } else {
    
            l = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Thank you for reading