思路解析 问题本质 在 k×k 网格中，沿网格线切割将其分成两个连通且全等的部分。给定 n 个相邻格子对，求最多能选多少对使它们都在同一部分内。 关键观察 观察 1：有效切割一定是 180° 中心对称的。 k 为偶数，网格中心恰好是格线交点 (k/2, k/2)。要使两部分全等，切割路径必须关于中心 180° 对称。因此切割路径从边界经过中心到对面边界。 观察 2：转化为最短路。 一个相邻格子对"不被满足"当且仅当两格之间的格线段在切割路径上。我们希望最小化被切割的对数，答案就是 n 减去这个最小值。 观察 3：利用对称性减半。 由于路径 180° 对称，只需确定从中心到边界的半条路径，另一半由对称决定。对于半路径上的每条格线段 e，它和它的 180° 对称边 mirror(e) 同时出现在完整路径上，代价为 count(e) + count(mirror(e))。 算法 1. 统计每条格线段被多少个输入对跨越 2. 构建格线交点图，每条边权 = 自身计数 + 对称边计数 3. 从中心 (k/2, k/2) 跑 Dijkstra 到任意边界点 4. 答案 = n − 最短路距离 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 坐标映射详解 格线交点用 (i, j) 表示，0≤i,j≤k0 \le i, j \le k0≤i,j≤k。 输入对 → 格线段： * 水平相邻对 (r, c₁)-(r, c₂)（c₂=c₁+1）→ 竖直格线段 down_edge(r−1, c₁) * 竖直相邻对 (r₁, c)-(r₂, c)（r₂=r₁+1）→ 水平格线段 right_edge(r₁, c−1) 180° 对称映射： * right_edge(i, j) 的对称边 = right_edge(k−i, k−j−1) * down_edge(i, j) 的对称边 = down_edge(k−i−1, k−j) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 逐行注释代码