起晚了，第一轮 Kickstart 没打上，补一下第二题。

入土选手码力下降，TvT 咕鸽还是强啊

题目

Parcels (Round A - Kick Start 2019)

题意

给一个$n×m$的01字符地图，1代表邮局，0代表空地。现在可以增加至多一个邮局，使得所有空白点到最近邮局曼哈顿距离最大值最小。求这个最小值k。

有$T$组输入，$T\le 100$，$n,m\le 250$

题解

首先特判答案$k=0$的情况，即地图中1的个数$\ge n×m−1$
将题意转化，求最小的k，每一个邮局覆盖距其k个曼哈顿距离以内的所有点，之后再加一个邮局可以使得地图被完全覆盖。

显然这个邮局是不加白不加的。考虑从1枚举最小值k，每枚举一次用 BFS 在地图上拓展每一个邮局的覆盖范围。此处的 BFS 初始时将所有邮局坐标入队，地图上的一个点不会二次入队。

然后判断剩余的未被覆盖的点是否可以找到一个点，到这个点的距离都$\le k$。如果找得到，那当前枚举到的k就是答案。

暴力地判断上述是否可以问题，需要枚举地图每个点和每个未覆盖点，复杂度$O(n^2m^2)$，但是未被覆盖的点有一大部分是不需要判断的。

想到只需选取离未被覆盖的点集中心最远的那部分点判断即可。此处的结论是，只需要判断未被覆盖的点集中横坐标和纵坐标和/差取到最大/最小值的点即可。最远的点数量是个常数，因此复杂度降为$O(nm)$。

最后复杂度$O(Tnm×玄学)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
const int d[][2]={0,1,0,-1,1,0,-1,0};
int n,m;
char a[255][255];
int main(){
  int T,kase=0;
  cin>>T;
  for (kase=1;kase<=T;kase++){
    cin>>n>>m;
    queue<pair<int,int>>q;
    for (int i=0;i<n;i++)
      for (int j=0;j<m;j++){
        cin>>a[i][j];
        if (a[i][j]=='1')q.push({i,j});
      }
    if (q.size()>=n*m-1){
      printf("Case #%d: %d\n",kase,0);
      continue;
    }
    for (int k=1;;k++){
      int len=q.size();
      for (int ii=0;ii<len;ii++){
        auto t=q.front();q.pop();
        for (int i=0;i<4;i++){
          int tx=t.first+d[i][0],ty=t.second+d[i][1];
          if (tx>=0&&ty>=0&&tx<n&&ty<m&&a[tx][ty]!='1'){
            a[tx][ty]='1';
            q.push({tx,ty});
          }
        }
      }
      vector<int> ax,ay;
      int maxp=-1e9,maxm=-1e9,minp=1e9,minm=1e9;
      for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
          if (a[i][j]!='1'){
            ax.push_back(i),ay.push_back(j);
            maxp=max(maxp,i+j);
            minp=min(minp,i+j);
            maxm=max(maxm,i-j);
            minm=min(minm,i-j);
          }
      if (ax.empty()){
        printf("Case #%d: %d\n",kase,k);
        break;
      }
      vector<int>mx,my;
      for (int i=0;i<ax.size();i++)
        if (ax[i]+ay[i]==maxp||ax[i]+ay[i]==minp||
            ax[i]-ay[i]==maxm||ax[i]-ay[i]==minm)
            mx.push_back(ax[i]),my.push_back(ay[i]);
      bool f=0;
      for (int xi=0;xi<n;xi++)
      for (int yi=0;yi<m;yi++){
        bool ff=0;
        for (int j=0;j<mx.size();j++)
          if (abs(xi-mx[j])+abs(yi-my[j])>k){
            ff=1;
            break;
          }
        if (!ff){
          f=1;
          break;
        }
      }
      if (f){
        printf("Case #%d: %d\n",kase,k);
        break;
      }
    }
  }
}