传送门

二分答案很好想，关键在于如何检查是否存在一个半径为r的“曼哈顿圆”能覆盖所有的空白点。

这里需要用到曼哈顿距离的另一个公式”dis(P_1,P_2) = \max{(|(x_1 + y_1) – (x_2 + y_2)|,|(x_1 – y_1) – (x_2 – y_2)|)}”

有了这个公式，发现只需要检查x+y的最大和最小，x-y的最大和最小，所对应的点是否满足即可。因为这四个点满足了其余点肯定是满足的

#include<bits/stdc++.h>
using namespace std;
const int maxn = 255;
typedef pair<int,int> pii;
vector<pii> e;
int n,m;
int mp[maxn][maxn];
bool vis[maxn][maxn];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
void bfs(int k)
{
    memset(vis, 0, sizeof vis);
    queue<pair<int,pii> > q; 
    for(auto i : e) q.push({0, i}), vis[i.first][i.second] = 1;
    while(q.size())
    {
        pii s = q.front().second;
        int t = q.front().first;
        q.pop();
        if(t == k) continue;
        int x = s.first, y = s.second;
        for(int i = 0; i < 4; i++)
        {
            int dx = x + dir[i][0], dy = y + dir[i][1];
            if(dx > 0 && dx <= n && dy > 0 && dy <= m && vis[dx][dy] == 0)
            {
                vis[dx][dy] = 1;
                q.push({t + 1,{dx, dy}});
            }
        }
    }
}
int dist(pii xxx, pii yyy)
{
    int ax = xxx.first, ay = xxx.second, bx = yyy.first, by = yyy.second;
    return max(abs(ax + ay - (bx + by)), abs(ax - ay - (bx - by)));
}
bool cmp1(const pii &x, const pii &y)
{
    return x.first + x.second < y.first + y.second;
}
bool cmp2(const pii &x, const pii &y)
{
    return x.first - x.second < y.first - y.second;
}
int main()
{
    int T; cin >> T;
    for(int cas = 1; cas <= T; cas++)
    {
        e.clear();
        char s[maxn];
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
        {
            scanf("%s", s + 1);
            for(int j = 1; j <= m; j++)
            {
                mp[i][j] = s[j] - '0';
                if(mp[i][j]) e.push_back({i, j});
            }
        }
        int l = 0, r = n + m;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            bfs(mid);
            vector<pii> a, b;
            for(int i = 1; i <= n; i++) 
                for(int j = 1; j <= m; j++)
                {
                    if(vis[i][j] == 0)
                    {
                        a.push_back({i, j});
                        b.push_back({i, j});
                    }
                }
            sort(a.begin(), a.end(), cmp1);
            sort(b.begin(), b.end(), cmp2);
            int res = 0, flag = 1;
            //cout<<a.size()<<endl;
            if(a.size()) //这里被自己坑了半天
            for(int i = 1; i <= n; i++)
            {
                for(int j = 1; j <= m; j++)
                {
                    flag = 0;
                    if(mp[i][j] == 0)
                    {
                        flag = 0;
                        pii pp ;
                        pp.first = i; pp.second = j;
                        res = max(max(dist(a[0], pp), dist(a.back(), pp)),max(dist(b[0], pp), dist(b.back(), pp)));
                        if(res <= mid)
                        {
                            flag = 1;
                            break;
                        }
                    }
                }
                if(flag) break;
            }
            if(flag) r = mid;
            else l = mid + 1;
        }
        //cout << l - 1 << endl;
        printf("Case #%d: %d\n", cas, l);
    }
}