D. 曼哈顿圆 – 详细题解

问题描述

给定一个 $n \times m$ 的网格，其中一些格子被标记为 #。已知这些 # 恰好构成了一个完整的曼哈顿圆，即存在一个圆心 $(h,k)$ 和一个正整数半径 $r$，使得一个格子 $(a,b)$ 是 # 当且仅当 $|h-a| + |k-b| < r$。保证这样的圆存在且唯一。要求输出圆心的坐标 $(h,k)$。

关键性质

曼哈顿距离 $|h-a| + |k-b|$ 可以写为：

$$|h-a| + |k-b| = \max\big( (h+k) - (a+b),\; (a+b) - (h+k),\; (h-k) - (a-b),\; (a-b) - (h-k) \big) $$

但这个形式不如直接利用坐标变换来得简洁。引入新变量：

$$u = a + b,\quad v = a - b.$$

则曼哈顿距离变为：

$$|h-a| + |k-b| = \max\big( |u - (h+k)|,\; |v - (h-k)| \big) $$

实际上，这是一个更常见的关系：在旋转 $45^\circ$ 并缩放后的坐标系中，曼哈顿圆会变成轴对齐的正方形。具体来说，定义：

$$U = a + b,\quad V = a - b.$$

那么条件 $|h-a| + |k-b| < r$ 等价于：

$$|U - (h+k)| < r \quad \text{且} \quad |V - (h-k)| < r. $$

这是因为曼哈顿距离可以分解为两个一维的切比雪夫距离（$L_\infty$ 距离）的叠加。更严格地说：

$$|h-a| + |k-b| = \max\big( |(h+k)-(a+b)|,\; |(h-k)-(a-b)| \big). $$

但上面等号并不成立？实际上，曼哈顿距离与切比雪夫距离之间有一个旋转关系：设 $x=a+b$, $y=a-b$，则 $|h-a|+|k-b| = \max(|x-(h+k)|, |y-(h-k)|)$ 吗？我们验证：取 $a=0,b=0$, $h=1,k=0$，左边 $=1$，右边 $x=0$, $h+k=1$, $| -1|=1$；$y=0$, $h-k=1$, $| -1|=1$，$\max=1$，成立。另一个例子：$a=1,b=0,h=1,k=1$，左边 $=|0|+| -1|=1$，右边 $x=1$, $h+k=2$, $| -1|=1$；$y=1$, $h-k=0$, $|1|=1$，$\max=1$。一般地，有恒等式：

$$|h-a|+|k-b| = \max\big( |(h+k)-(a+b)|,\; |(h-k)-(a-b)| \big). $$

这个等式成立吗？考虑 $a=2,b=0,h=0,k=0$，左边 $=2$，右边 $x=2$, $h+k=0$, $|2|=2$；$y=2$, $h-k=0$, $|2|=2$，$\max=2$，成立。再试 $a=1,b=1,h=0,k=0$，左边 $=2$，右边 $x=2$, $|2|=2$；$y=0$, $|0|=0$，$\max=2$，成立。实际上，这个等式是正确的，因为：

$$|h-a|+|k-b| = \max_{s,t\in\{-1,1\}} \big( s(h-a) + t(k-b) \big) = \max\big( |(h+k)-(a+b)|,\; |(h-k)-(a-b)| \big). $$

因此，曼哈顿圆 $\{ (a,b): |h-a|+|k-b| < r \}$ 在 $(U,V)$ 坐标系下变为：

$$\{ (U,V): |U - U_0| < r,\; |V - V_0| < r \},$$

其中 $U_0 = h+k$, $V_0 = h-k$。即它是一个轴对齐的正方形（边长为 $2r-1$ 的整数格子点集）。

算法思路

因为网格上的 # 点正好是这个正方形内的所有整数点（注意 $U = a+b$, $V=a-b$ 的奇偶性：$U$ 和 $V$ 同奇偶，因为 $a = (U+V)/2$, $b=(U-V)/2$ 必须是整数。但题目保证存在完整的曼哈顿圆，意味着这些 $(U,V)$ 恰好构成一个 $r \times r$ 的正方形（边界为 $<r$，所以实际点集是 $|U-U_0| \le r-1$ 且 $|V-V_0| \le r-1$ 且满足同奇偶约束。但圆心 $(h,k)$ 是整数，所以 $U_0$ 和 $V_0$ 同奇偶，正方形内的点自然满足同奇偶，因此所有满足不等式的格点都会出现。

因此，我们只需要找到所有 # 点对应的 $U$ 和 $V$ 的最小值和最大值，就可以确定正方形的范围：

$$U_{\min} = \min_{(a,b)\in \text{#}} (a+b),\quad U_{\max} = \max_{(a,b)\in \text{#}} (a+b), $$$$V_{\min} = \min_{(a,b)\in \text{#}} (a-b),\quad V_{\max} = \max_{(a,b)\in \text{#}} (a-b). $$

由于正方形关于中心对称，我们有：

$$U_0 = \frac{U_{\min} + U_{\max}}{2},\qquad V_0 = \frac{V_{\min} + V_{\max}}{2}. $$

注意 $U_{\min}$ 和 $U_{\max}$ 的奇偶性相同（因为正方形内点的 $U$ 值连续且步长为 $2$？实际上，如果圆心整数，则 $U_0$ 整数，且 $U_{\min}=U_0-(r-1)$，$U_{\max}=U_0+(r-1)$，它们的和是 $2U_0$，是偶数，所以平均值是整数。同样 $V$ 亦然。

最后，由 $U_0 = h+k$ 和 $V_0 = h-k$ 解得：

$$h = \frac{U_0 + V_0}{2},\qquad k = \frac{U_0 - V_0}{2}. $$

由于 $U_0$ 和 $V_0$ 同奇偶，$h,k$ 均为整数。

实现步骤

1. 读入网格，遍历每个格子。
2. 如果格子是 #，计算 $u = i + j$（注意坐标从 $1$ 开始，即行号 $i$，列号 $j$），计算 $v = i - j$。
3. 维护 $u$ 的最小值 $u_{\min}$ 和最大值 $u_{\max}$，以及 $v$ 的最小值 $v_{\min}$ 和最大值 $v_{\max}$。
4. 计算 $U_0 = (u_{\min}+u_{\max})/2$，$V_0 = (v_{\min}+v_{\max})/2$。
5. 计算 $h = (U_0 + V_0)/2$，$k = (U_0 - V_0)/2$。
6. 输出 $h$ 和 $k$。

时间复杂度

每个测试用例需要扫描整个网格，即 $O(nm)$。所有测试用例的总格子数不超过 $2\times 10^5$，因此总时间 $O(\sum nm)$，非常快。

正确性证明

由曼哈顿圆的定义及坐标变换可知，所有 # 点在 $(U,V)$ 空间下构成一个轴对齐的正方形，其边界由极值唯一确定。因此，通过极值计算出正方形的中心 $(U_0,V_0)$，再逆变换即得圆心 $(h,k)$。由于保证存在完整的曼哈顿圆，该过程必然得到正确结果。

示例验证

以第一个样例：$5\times5$ 网格，中间一个 #。那么 $u_{\min}=u_{\max}=3+3=6$，$v_{\min}=v_{\max}=3-3=0$，则 $U_0=6$，$V_0=0$，$h=(6+0)/2=3$，$k=(6-0)/2=3$，输出 $(3,3)$，正确。

第二个样例：标准菱形。计算所有 # 点的 $u$ 和 $v$ 极值，可得相同结果。

结论

该解法利用了曼哈顿圆在 $45^\circ$ 旋转坐标系下变为正方形的特性，通过极值快速求解圆心，实现简单且高效。