洛谷P1902 刺杀大使

题目

二分加广搜

#include <bits/stdc++.h>
using namespace std;
int n, m, l, r, p[1001][1001], vis[1001][1001];
int dx[6] = {0, 1, -1, 0, 0};
int dy[6] = {0, 0, 0, 1, -1};
int qx[100100], qy[1001001];
bool check(int d)
{
    memset(vis, 0, sizeof(vis));
    int front = 0, tail = 0;
    for (int i = 1; i <= m; i++)
        qx[++tail] = i, qy[tail] = 1;
    int tot = 0;
    while (front <= tail)
    {
        int nx = qx[front], ny = qy[front++];
        if (ny == n)
            tot++;
        for (int i = 1; i <= 4; i++)
        {
            int ax = nx + dx[i];
            int ay = ny + dy[i];
            if (p[ay][ax] <= d && !vis[ay][ax] && (ax <= m && ax >= 1 && ay <= n && ay >= 1))
                qx[++tail] = ax, qy[tail] = ay, vis[ay][ax] = 1;
        }
    }
    if (tot == m) return 1;
    return 0;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &p[i][j]), r = max(r, p[i][j]);
    int mid = 0, ans = 0;

    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (check(mid))
            ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf("%d", ans);
    return 0;
}