题解：P16724 [GKS 2019 #A] Parcels

· · 题解

注意到题目中出现了「最大值的最小值」这样的表述，考虑二分答案 k，即：找到最小的 k，使得当添加一个快递办公室后，对于每个格子，都能找到一个快递办公室，使得两者之间的曼哈顿距离不超过 k。

然而这并不好判定。考虑找出离每个办公室曼哈顿距离不超过 k 的格子集合，我们称其为这一办公室的「覆盖范围」。简单画图可得，在不考虑超出网格范围的前提下，它们构成了一个以这一办公室为中心，旋转了 45^\circ 的正方形。那么，「对于每个格子，都能找到一个快递办公室，使得两者之间的曼哈顿距离不超过 k」就可以重新表述为：每个格子都至少在一个办公室的覆盖范围中。

为了获取每个格子的覆盖范围，可以想到二维差分，然而，处理旋转了 45^\circ 的正方形是非常不便的。不妨将整个坐标系旋转 45^\circ，这样，每个办公室的覆盖范围就变成了以这个办公室为中心，边长为 2k 的，各边与坐标轴平行或垂直的正方形。

具体地，记每个格子原有的坐标为 (x, y)，旋转坐标系后的坐标为 (x', y')，有

\begin{align*} x' &= x - y + 250, \\ y' &= x + y - 1,\\ x &= \frac{x' + y' - 249}{2},\\ y &= \frac{y' - x' + 251}{2}. \end{align*}

这样可以将每个格子的横纵坐标映射在 [1, 249] 之间，方便实现。

使用差分得到现有的覆盖范围可以覆盖哪些格子之后，我们找出没有被覆盖的格子的横、纵坐标的最小值 x_{\min}, y_{\min} 和最大值 x_{\max}, y_{\max}。显然，如果 x_{\max} - x_{\min} > 2k 或 y_{\max} - y_{\min} > 2k，那么无论如何，也找不到一个如上所述的正方形，与已有的覆盖范围一起，将整个网格覆盖。否则，如果有未被覆盖的网格坐标 (x, y) 满足

\begin{align*} x &\ge x_{\max} - k,\\ x &\le x_{\min} + k,\\ y &\ge y_{\max} - k,\\ y &\le y_{\min} + k, \end{align*}

那么它就可以作为一个新办公室的位置。如果不能找到这样的坐标，就说明此时的 k 是不可行的。 :::info[代码]

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const int INF = 0x3f3f3f3f, _INF = 0xc0c0c0c0;
const ll LLINF = 0x3f3f3f3f3f3f3f3f, _LLINF = 0xc0c0c0c0c0c0c0c0;

namespace IO {
// 略
} // namespace IO
using IO::err; using IO::read; using IO::write;

const int N = 255;
int T, R, C;
int d[N * 2][N * 2];
int p[N * N][2], cnt;
int Case;

bool check(int k) {
  memset(d, 0, sizeof(d));
  for (int i = 1; i <= cnt; i++) {
    int x = p[i][0], y = p[i][1];
    d[std::max(x - k, 1)][std::max(y - k, 1)]++;
    d[std::max(x - k, 1)][std::min(y + k + 1, 500)]--;
    d[std::min(x + k + 1, 500)][std::max(y - k, 1)]--;
    d[std::min(x + k + 1, 500)][std::min(y + k + 1, 500)]++;
  }

  for (int i = 1; i <= 499; i++) {
    for (int j = 1; j <= 499; j++) {
      d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];
    }
  }

  int minx = INF, maxx = 0, miny = INF, maxy = 0; 
  for(int i = 1; i <= 499; i++) {
    bool ok = false;
    for (int j = 1; j <= 499; j++) {
      // 先转回原坐标系检验。
      if (((i + j) & 1) == 0) continue;
      int mx = (i + j - 249) >> 1, my = (j - i + 251) >> 1;
      if (mx <= 0 || mx > R || my <= 0 || my > C) continue;
      if (d[i][j] == 0) {
        minx = std::min(minx, i);
        miny = std::min(miny, j);
        maxx = std::max(maxx, i);
        maxy = std::max(maxy, j);
      }
    }
  }

  if (maxx - minx > 2 * k || maxy - miny > 2 * k) {
    return false;
  }

  for (int i = 1; i <= R; i++) {
    for (int j = 1; j <= C; j++) {
      int x = i - j + 250, y = i + j - 1;
      if (x >= maxx - k && x <= minx + k && y >= maxy - k && y <= miny + k) {
        return true;
      }
    }
  }

  return false;
}

void solve() {
  Case++;
  cnt = 0;
  read(R, C);
  for (int i = 1; i <= R; i++) {
    for (int j = 1; j <= C; j++) {
      char ch;
      read(ch);
      if (ch == '1') {
        p[++cnt][0] = i - j + 250; p[cnt][1] = i + j - 1;
      }
    }
  }

  int l = 0, r = 500;
  while (l < r) {
    int mid = (l + r) >> 1;

    if (check(mid)) {
      r = mid;
    } else l = mid + 1;
  }

  write("Case #", Case, ": ", l, '\n');
}

int main() {
  read(T);
  while (T--) solve();

#ifdef CLOCK
  std::cerr << "\033[95m" << clock() * 1.0 / CLOCKS_PER_SEC << "s\n\033[90m";
#endif
  return 0;
}

:::