更新题目 Min Inconvenience：加配送中心
题目 amazon-min-inconvenience · 修改（rev 5） · · 2026-10-27 00:33
body
@@ -1,54 +1,92 @@ +## TL;DR + +- 题目要的是让最远的那个普通位置离中心尽量近（min-max），距离按切比雪夫距离算，也就是允许斜着走（「题目」）。 +- 先用 8 个方向的多源 BFS 算出每格到最近现有中心的距离（「先算每格到最近中心的距离」）。 +- 再二分答案 $D$：距离大于 $D$ 的格子都要被新中心覆盖，只要它们的包围盒高和宽都不超过 $2D$ 就可行（「判断一个上限是否可行」）。 +- 时间 $O(nm \log \max(n, m))$，500×500 在这里实测 1 秒以内（「复杂度」）。 +- 易错的地方：BFS 只走 4 个方向、贪心地把新中心放在最远的点上、网格里一个中心都没有、二分下界没从 0 开始（「易错点」）。 +- 考场上先写暴力解保底，再写二分（「面经里怎么考的」）。 + ## 题目 -城市是一个 `n × m` 的 0/1 网格（`1 ≤ n, m ≤ 500`），值为 1 的格子是配送中心（delivery center），值为 0 的格子是普通位置。两格 `(x1, y1)`、`(x2, y2)` 之间的距离用切比雪夫距离（Chebyshev distance）`max(|x1-x2|, |y1-y2|)` 来算，也就是行差和列差里取较大的那个。直观地说，它相当于每一步可以往 8 个方向（包括对角线方向）走一格，每走一步算 1，例如 `(1,2)` 和 `(0,4)` 的距离是 `max(1, 2) = 2`。每个 0 到离它最近的 1 都有一个距离，这些距离里的最大值就是整个网格的「不便度」（inconvenience），也就是离配送中心最远的那个普通位置到底有多远。 - -你最多可以把一个 0 改成 1，也就是在任意一个普通位置新开一个配送中心，要求返回改完之后能达到的最小不便度。函数签名是 `int getMinInconvenience(int grid[n][m])`。 - -- 样例 1 是 `[[0,0,0,1],[0,0,0,1]]`。各格到最近中心的距离是 `3 2 1 0 / 3 2 1 0`（斜杠隔开两行），初始不便度是 3；把 `(0,0)` 改成 1 之后，距离变成 `0 1 1 0 / 1 1 1 0`，所以返回 **1**。 -- 样例 2 是 `3 × 4` 的全 0 网格，最好的做法是把 `(1,1)` 改成 1，返回 **2**。这个样例说明，网格一开始可以一个配送中心都没有。 -- 一亩三分地（北美华人留学和求职论坛）站方的 AI 整理区（下文叫「站方 AI」）还补过一个样例 `[[1,0,0],[0,0,0],[0,0,0]] → 1`。它是站方 AI 整理的，未经原帖证实；不过用本页的代码和暴力解（brute force，把每种改法都试一遍）算出来也是 1。 -- 网格里没有 0（全是 1）时怎么算，原帖没说。按定义，这时没有需要算距离的格子，取 0【推断】。 - -### 2026-06 的另一种说法 - -有一篇原帖只写了「最多把一个 0 变成 1，找最小的从 0 到 1 的距离」，没有给出距离的定义。有人回帖指出，照字面理解的话直接返回 1 就行（只要网格里同时有 0 和 1，总有一个 0 紧挨着某个 1，所有距离里最小的就是 1），所以题目要的应该是 min-max，也就是让最远的那个距离尽量小。发帖人在回复里举了个例子 `[[0,0,0,0],[0,0,0,1]]`：不改时各格的距离是 `4 3 2 1 / 3 2 1 0`，最远是 4；把左上角改成 1 之后是 `0 1 2 1 / 1 2 1 0`，最远是 2。这组数字是按只能上下左右走算出来的，也就是曼哈顿距离（Manhattan distance，行差的绝对值加列差的绝对值）。 - -把每一格都试着改一遍、暴力算出结果，可以看到：按曼哈顿距离，左边 2×2 的四格改哪一格结果都是 2，发帖人改左上角正是最优解；按切比雪夫距离，这个网格初始的最远距离是 3，最优答案是 1，同样是左边 2×2 的四格任选一格都行，也包括发帖人改的左上角。这篇帖子的题意「最多改一个 0、让最远距离最小」和本题一致，例子的形状也像官方样例，所以【推断】是同一道题：发帖人选的格子没错，只是距离按曼哈顿算了（或者记错了距离的定义）。考前按切比雪夫距离准备，考场上先看清题面给的距离公式；曼哈顿版本的解法见 Follow-up。 +城市是一个 $n \times m$ 的 0/1 网格（$1 \le n, m \le 500$）。值为 1 的格子是配送中心（delivery center），值为 0 的格子是普通位置。两格 $(x_1, y_1)$、$(x_2, y_2)$ 之间的距离是切比雪夫距离（Chebyshev distance）： + +$$ +\max(|x_1 - x_2|, |y_1 - y_2|) +$$ + +也就是行差和列差里取较大的那个。它相当于每一步可以往 8 个方向（包括 4 个斜方向）走一格，每步算 1。例如 $(1, 2)$ 和 $(0, 4)$ 的距离是 $\max(1, 2) = 2$。 + +每个 0 到离它最近的 1 有一个距离，这些距离里的最大值叫整个网格的「不便度」（inconvenience），也就是离配送中心最远的那个普通位置有多远。你最多可以把一个 0 改成 1（新开一个配送中心），返回改完之后能达到的最小不便度。函数签名是 `int getMinInconvenience(int grid[n][m])`。 + +- 样例 1：`[[0,0,0,1],[0,0,0,1]]`。各格到最近中心的距离是 `3 2 1 0 / 3 2 1 0`（斜杠隔开两行），初始不便度是 3。把 `(0,0)` 改成 1 之后，距离变成 `0 1 1 0 / 1 1 1 0`，返回 **1**。 +- 样例 2：3×4 的全 0 网格，把 `(1,1)` 改成 1 最好，返回 **2**。这个样例说明网格一开始可以一个配送中心都没有。 +- 网格里全是 1、没有 0 时怎么算，原帖没说。按定义这时没有要算距离的格子，取 0【推断】。 + +### 2026-06 那篇帖子的另一种说法 + +有一篇原帖只写了「最多把一个 0 变成 1，找最小的从 0 到 1 的距离」，没给距离的定义。照字面读，只要网格里同时有 0 和 1，总有一个 0 紧挨着某个 1，答案永远是 1，所以回帖的人指出题目要的应该是 min-max。发帖人在回复里举了 `[[0,0,0,0],[0,0,0,1]]`：不改时最远是 4，把左上角改成 1 后最远是 2。这组数字是按只能上下左右走算的，也就是曼哈顿距离（Manhattan distance，行差绝对值加列差绝对值）。 + +用暴力解把每一格都试改一遍：按曼哈顿距离，左边 2×2 的四格改哪格都是 2，发帖人改左上角是最优的。按切比雪夫距离，这个网格初始最远是 3，最优是 1，同样是左边 2×2 任选一格。题意「最多改一个 0、让最远距离最小」和本题一致，所以【推断】是同一道题，发帖人把距离按曼哈顿算了（或者记错了定义）。考前按切比雪夫准备，考场上先看清题面给的距离公式，曼哈顿版本的做法见「Follow-up」。 ## 面经里怎么考的 -### OA 的结构 - -这道题是 OA 里的编程题，排在第一题（帖子里叫「q1」），后面接一道 AI 辅助的工程题，见 [[q:amazon-oa-ai-debug]]。2026-08 底有一篇写明整场 OA 是 100 分钟、两道题。还有一篇说，AI 题之后另有一组选择题，考的是 BQ（behavioral question，行为面试题）、LP（Leadership Principles，Amazon 的领导力准则）和系统设计。 - -### 谁考到过，结果怎样 - -从 2026-06 底到 09 中旬一直有人考到这道题。考生里既有在职跳槽的，也有应届生；应届生里既有找全职的，也有找实习的。8 月中旬一位在职跳槽的发帖人贴了英文题面，用词是 delivery center 和 inconvenience，带约束和样例 1；9 月中旬一位应届发帖人贴了函数签名和全 0 的样例 2。 - -8 月中旬那位在职跳槽的发帖人说「感觉不太简单」。8 月底一位应届发帖人觉得「有难度」，在回复里说这题很难，做出来都不一定能过；不过这位发帖人自己的 OA 结果是通过。8 月下旬一位找实习的发帖人写出了完整思路：先用多源 BFS 算距离，再对答案二分，最后对离现有中心太远的那些格子求范围的交集（这几个概念在下文「思路」一节解释）。结果还是没通过，帖子里没说是因为什么没通过。 - -6 月底那位在职跳槽的发帖人（就是「题目」一节里 2026-06 那篇帖子的发帖人）钻了牛角尖，卡在一个走不通的思路上，连暴力解都没写出来；后面的 AI 题倒是在 60 分钟里刚好全部通过测试，但最后 recruiter 还是通知没通过。这位发帖人还在回复里说考试时不用开摄像头；别的帖子里也有人问过要不要开，但没人回答。 - -同一帖的回复里，另一位考生说这题比「雾寺儿」多了一次翻转（也就是可以新开一个配送中心）。「雾寺儿」是用谐音写的题号，【推断】指 LeetCode 542（01 Matrix，[[q:lc542]]）。这位考生说自己「还有五个超时」，后面的 AI 题只修好了一个，很快就被拒了。这条只能算旁证，因为说的人不是发帖人本人；【推断】这里的超时指的就是这道编程题。 - -### 考场上怎么做 - -建议先花几分钟写一个暴力解保底：每个 0 都试着改一次，再跑一遍 BFS 算不便度，取其中最小的；然后再去写二分。【推断】这样做有用的前提是 OA 按通过的测试用例给分，暴力解至少能拿到一部分分。原帖没明说 OA 怎么给分，只有上面那句「还有五个超时」能间接说明。暴力解的复杂度是 `O((nm)^2)`，500×500 的网格肯定超时，所以要全部通过，正解必须是 BFS + 二分（或者 Follow-up 里的线性做法）。 - -大家认可的做法是先用多源 BFS 算出每格的基础距离，再二分答案。8 月中旬一位发帖人说，这是一亩三分地上出现过的面经题，建议考前把代码自己写一遍，可以用原帖提到的 CodeSignal（一个在线编程测评平台）whiteboard 功能练习；OA 用的平台是不是 CodeSignal，原帖没明说。 +这是 Amazon OA 里的编程题。有帖子说它是第一题（帖子里叫「q1」），后面接一道 AI 辅助的工程题（见 [[q:amazon-oa-ai-debug]]）。2026-08 底有一篇写明整场 100 分钟、两道题，还有一篇说 AI 题之后另有一组选择题，考 BQ（behavioral question，行为面试题）、LP（Leadership Principles，Amazon 的领导力准则）和系统设计。2026-10 那篇帖子的发帖人在回复里贴了英文原题，只提到这一道编程题，所以 OA 的整体结构以你收到的说明为准。 + +发帖时间从 2026-06 到 2026-10 都有，考生里有在职跳槽的，也有找全职和找实习的应届生。8 月中旬一位在职跳槽的发帖人贴了英文题面（用词是 delivery center 和 inconvenience）、约束和样例 1，9 月中旬一位应届发帖人贴了函数签名和全 0 的样例 2。 + +几位考生对难度和结果的说法： + +- 8 月中旬那位在职跳槽的发帖人说「感觉不太简单」。 +- 8 月底一位应届发帖人觉得「有难度」，回复里说做出来都不一定能过，不过这位发帖人自己的 OA 结果是通过。 +- 8 月下旬一位找实习的发帖人写出了完整思路（多源 BFS 算距离、二分答案、对远格子的范围求交集，下面「思路」会讲），结果还是没通过，帖子没说原因。 +- 6 月底那位发帖人（就是上面「另一种说法」那篇）卡在一个走不通的思路上，连暴力解都没写出来。后面的 AI 题在 60 分钟里全部通过测试，最后 recruiter 还是通知没过。这位发帖人还说考试不用开摄像头（别的帖子也有人问过，没人回答）。 +- 同一帖的回复里另一位考生说，这题是「雾寺儿」（谐音题号，【推断】指 LeetCode 542，[[q:lc542]]）多了一次翻转。这位考生「还有五个超时」（【推断】指这道编程题），AI 题只修好一个，很快被拒。 + +考场上建议先花几分钟写暴力解保底：每个 0 试改一次，重新算一遍不便度，取最小，然后再写二分。【推断】这样做有用的前提是 OA 按通过的测试用例给分，原帖没明说，只有上面「还有五个超时」能间接说明。暴力解在 500×500 上一定超时（见「朴素做法」），要全部通过只能用 BFS 加二分。8 月中旬一位发帖人说这是一亩三分地（北美华人留学和求职论坛）上出现过的面经题，建议考前自己写一遍，可以用原帖提到的 CodeSignal（一个在线编程测评平台）的 whiteboard 功能练。OA 用的是不是 CodeSignal，原帖没明说。 ## 思路 -整体分两步。第一步先不加新中心，算出每个格子离最近的现有中心有多远。第二步用二分答案（binary search on the answer）：猜一个不便度的上限 D，检查「只加一个中心，能不能让每个普通位置离最近中心都不超过 D」，能做到就试更小的 D，做不到就试更大的 D，直到找出能做到的最小 D。之所以能这样二分，是因为可行性单调，见最后一条。 - -1. **先用多源 BFS 算出每格的基础距离。** 普通 BFS 从一个起点出发；多源 BFS（multi-source BFS）一开始就把所有起点一起放进队列，这里的起点就是所有的 1。这样每个格子第一次被访问到时，记下的步数就是它到最近那个起点的距离。因为切比雪夫距离下斜着走一步也只算一步，BFS 每一步要往 8 个方向扩展，这样得到的步数正好就是每格到最近中心的切比雪夫距离（Chebyshev distance），记作 `d`。这一步和 [[q:lc1162]] 的做法相同，只是扩展方向换成了 8 个。如果网格里一个 1 都没有，BFS 什么也访问不到，`d` 全部保持「无穷大」。 -2. **二分时，要判断一个候选 D 是否可行。** 判断的问题是：只加一个中心，能不能让不便度 ≤ D。`d ≤ D` 的格子已经满足要求，不用管；`d > D` 的格子（下文叫「远格子」）必须全部落在新中心的 D 范围以内。到某个格子切比雪夫距离 ≤ D 的所有位置，组成一个以它为中心、边长 `2D+1` 的正方形，所以问题变成：这些正方形有没有公共的格子。行和列可以分开看。一个在第 `x` 行的远格子，要求新中心的行落在 `[x - D, x + D]` 里；所有远格子的这些区间取交集，就是行要落在 `[xmax - D, xmin + D]`。列同理，要落在 `[ymax - D, ymin + D]`。这里的 `xmin`、`xmax`、`ymin`、`ymax` 是远格子行坐标、列坐标的最小值和最大值，所以判断时只需要维护这四个数，不用记下每个远格子。 -3. **判断条件可以进一步化简。** 区间 `[xmax - D, xmin + D]` 非空，就是 `xmax - D ≤ xmin + D`，移项后正是 `xmax - xmin ≤ 2D`；列同理是 `ymax - ymin ≤ 2D`。这两个跨度就是远格子的包围盒（bounding box，能框住所有远格子的最小矩形）的高和宽（按坐标差算）。条件满足时，新中心放在包围盒的中点 `((xmin+xmax)//2, (ymin+ymax)//2)` 就行：中点到两端的距离最多是跨度的一半向上取整；跨度是整数且 ≤ 2D，所以这个距离不超过 D，中点一定在交集里。中点又夹在两个真实存在的格子坐标之间，一定在网格里，所以不用另外和网格边界求交集。 -4. **选出来的位置一定是 0，可以合法地改。** 题目只允许把普通位置改成配送中心，所以要确认交集里没有原有的配送中心。用反证法：要是某个原有的 1 离所有远格子都 ≤ D，那么这些格子的 `d` 本来就 ≤ D，就不会是远格子，矛盾。另外，新中心那一格自己从 0 变成了 1，不再参与取最大值，只会让最大值更小，所以「改一个」永远不比「不改」差，直接按「改一个」算就行。 -5. **可行性是单调的，所以可以二分。** D 越大，远格子越少，每个正方形也越大，交集只会更容易非空；所以某个 D 可行时，比它大的 D 也一定可行。`D = max(n, m)` 一定可行，因为网格里任意两格的切比雪夫距离都小于 `max(n, m)`，新中心放在哪里都能覆盖所有格子，可以拿它当二分的上界。下界是 0，比如 `[[0]]`，把唯一那一格改掉之后就没有 0 了。 +### 朴素做法：每个 0 都试一遍 + +最直接的做法是把每个 0 都试着改成 1，每次跑一遍 BFS 算出不便度，取最小值。网格有 $nm$ 个格子，每次 BFS 是 $O(nm)$，合起来是 $O((nm)^2)$。500×500 时是 $6 \times 10^{10}$ 量级，在任何合理的时限里都跑不完。它的用处是保底拿分，以及在小数据上给正解对拍。 + +要更快，就要避免每个候选位置都重算一遍距离。下面的做法只算一次距离，再用二分答案把「新中心放哪」变成一个只看四个数的判断。 + +### 先算每格到最近中心的距离 + +普通 BFS 从一个起点出发。多源 BFS（multi-source BFS）一开始把所有起点一起放进队列，这里的起点是所有的 1。这样每个格子第一次被访问时记下的步数，就是它到最近那个 1 的步数。切比雪夫距离下斜走一步也算一步，所以 BFS 每一步往 8 个方向扩展，得到的步数正好是每格到最近中心的切比雪夫距离，下面记作 $d$。这一步和 [[q:lc1162]] 相同，只是方向换成 8 个。 + +网格里一个 1 都没有时，BFS 什么也访问不到，$d$ 全部保持一个比任何真实距离都大的值（代码里是 $n + m$）。 + +> [!say] First I run a multi-source BFS from all existing centers, moving in all eight directions, so every cell gets its Chebyshev distance to the nearest center. + +### 二分答案 + +二分答案（binary search on the answer）是指：猜一个不便度上限 $D$，判断「只加一个中心，能不能让每个普通位置离最近中心都不超过 $D$」。能做到就试更小的 $D$，做不到就试更大的，最后找到能做到的最小 $D$。 + +能这样二分，是因为可行性单调：$D$ 越大，需要新中心照顾的格子越少，每个格子允许的范围也越大，所以某个 $D$ 可行时，比它大的 $D$ 也可行。二分的上界取 $\max(n, m)$，网格里任意两格的切比雪夫距离都小于它，新中心放在哪都能覆盖全部格子。下界取 0，比如 `[[0]]` 把唯一那一格改掉之后就没有 0 了。 + +### 判断一个上限是否可行 + +给定 $D$，$d \le D$ 的格子已经满足要求，不用管。$d > D$ 的格子（下面叫「远格子」）必须全部落在新中心的 $D$ 范围以内。到某个格子切比雪夫距离不超过 $D$ 的所有位置，组成以它为中心、边长 $2D + 1$ 的正方形，所以问题变成：所有远格子的正方形有没有公共格子。 + +正方形可以按行、列分开看。第 $x$ 行的远格子要求新中心的行落在 $[x - D, x + D]$ 里，所有远格子的这些区间取交集，得到 + +$$ +[x_{\max} - D,\ x_{\min} + D] +$$ + +其中 $x_{\min}$、$x_{\max}$ 是远格子行号的最小值和最大值。这个区间非空，就是 $x_{\max} - D \le x_{\min} + D$，移项得 $x_{\max} - x_{\min} \le 2D$。列同理，条件是 $y_{\max} - y_{\min} \le 2D$。这两个跨度是远格子包围盒（bounding box，能框住所有远格子的最小矩形）的高和宽，所以判断时只需要维护四个数，代码里叫 `row_min`、`row_max`、`col_min`、`col_max`。 + +条件满足时，新中心放在包围盒中点 $(\lfloor (x_{\min} + x_{\max}) / 2 \rfloor, \lfloor (y_{\min} + y_{\max}) / 2 \rfloor)$ 就行。中点到两端的距离最多是跨度的一半向上取整，跨度是不超过 $2D$ 的整数，所以这个距离不超过 $D$。中点夹在两个真实格子的坐标之间，一定在网格里，所以不用再和网格边界求交集。 + +> [!say] Then I binary-search the answer D. For a candidate D, every cell still farther than D must be covered by the one new center, so the D-squares around those cells must intersect. I only track the min and max row and column of the far cells. D is feasible if both spans are at most 2D, and the new center goes at the middle of their bounding box. + +### 新中心一定能放在 0 上 + +题目只允许把 0 改成 1，所以要确认上面选出来的位置不是原有的中心。用反证法：假如某个原有的 1 离所有远格子都不超过 $D$，这些格子的 $d$ 本来就不超过 $D$，就不会是远格子，矛盾。另外，新中心那一格自己从 0 变成 1，不再参与取最大值，只会让最大值变小，所以「改一个」永远不比「不改」差，直接按「改一个」算就行。 ## 代码 - -这段代码已运行过。原帖的两个样例和「测试用例」一节里的边界用例，结果全部符合预期。另外写了一个暴力解：逐个试着改每个 0，再直接算所有 0 到所有 1 的距离。用它和下面的代码在 2500 组随机生成的小网格上对比结果（这种做法叫对拍），两边全部一致；这些网格的 n、m ≤ 8，其中包括一个中心都没有的网格和全是中心的网格。 ```python @@ -56,51 +94,53 @@ +def nearest_center_distances(grid, directions): + """多源 BFS：返回每格到最近 1 的步数，一个 1 都没有时全是 unreachable。""" + n, m = len(grid), len(grid[0]) + unreachable = n + m # 比任何真实距离都大 + dist = [[unreachable] * m for _ in range(n)] + queue = deque() + for r in range(n): + for c in range(m): + if grid[r][c] == 1: + dist[r][c] = 0 + queue.append((r, c)) + while queue: + r, c = queue.popleft() + for dr, dc in directions: + nr, nc = r + dr, c + dc + if 0 <= nr < n and 0 <= nc < m and dist[nr][nc] == unreachable: + dist[nr][nc] = dist[r][c] + 1 + queue.append((nr, nc)) + return dist + + +EIGHT_DIRECTIONS = [(dr, dc) for dr in (-1, 0, 1) for dc in (-1, 0, 1) + if (dr, dc) != (0, 0)] + + +def can_reach_limit(dist, limit): + """只加一个中心，能否让每格到最近中心都不超过 limit。""" + row_min = col_min = len(dist) + len(dist[0]) + row_max = col_max = -1 + for r, row in enumerate(dist): + for c, d in enumerate(row): + if d > limit: # 远格子，必须由新中心覆盖 + row_min, row_max = min(row_min, r), max(row_max, r) + col_min, col_max = min(col_min, c), max(col_max, c) + if row_max == -1: # 没有远格子 + return True + return row_max - row_min <= 2 * limit and col_max - col_min <= 2 * limit + + def get_min_inconvenience(grid): - n, m = len(grid), len(grid[0]) - INF = n + m # 比任何真实距离都大；一个 1 都没有时所有格子都是 INF - d = [[INF] * m for _ in range(n)] - q = deque() - for i in range(n): - for j in range(m): - if grid[i][j] == 1: - d[i][j] = 0 - q.append((i, j)) - # 多源 BFS：8 个方向各走一步算 1，得到的就是切比雪夫距离 - while q: - x, y = q.popleft() - nd = d[x][y] + 1 - for dx in (-1, 0, 1): - for dy in (-1, 0, 1): - nx, ny = x + dx, y + dy - if 0 <= nx < n and 0 <= ny < m and d[nx][ny] == INF: - d[nx][ny] = nd - q.append((nx, ny)) - - def feasible(D): - # d > D 的「远」格子都要落在同一个新中心的 D 范围内 - xmin = ymin = INF - xmax = ymax = -1 - for i in range(n): - row = d[i] - for j in range(m): - if row[j] > D: - if i < xmin: xmin = i - if i > xmax: xmax = i - if j < ymin: ymin = j - if j > ymax: ymax = j - if xmax == -1: # 没有远格子 - return True - # 各远格子的 (2D+1)×(2D+1) 方框求交：行 [xmax-D, xmin+D]，列 [ymax-D, ymin+D] - # 非空就行；交集一定包含远格子包围盒的中点，不会出网格 - return xmax - xmin <= 2 * D and ymax - ymin <= 2 * D - - lo, hi = 0, max(n, m) # hi 一定可行 - while lo < hi: - mid = (lo + hi) // 2 - if feasible(mid): - hi = mid + dist = nearest_center_distances(grid, EIGHT_DIRECTIONS) + low, high = 0, max(len(grid), len(grid[0])) # high 一定可行 + while low < high: + mid = (low + high) // 2 + if can_reach_limit(dist, mid): + high = mid else: - lo = mid + 1 - return lo + low = mid + 1 + return low @@ -110,23 +150,41 @@ ``` +BFS 把方向表当参数，是为了让「Follow-up」的曼哈顿版本复用它。 + +### 实测（2026-10-27，Python 3.13） + +对拍用的暴力解不跑 BFS，每个 0 都试改一次（也试不改），直接按定义算不便度，核心一行是 `max(min(metric(z, o) for o in ones) for z in zeros)`，`metric` 换成切比雪夫或曼哈顿距离。没有 0 时返回 0，有 0 没有 1 时返回无穷大。 + +- 两个原帖样例和「测试用例」表里的全部输入，结果都等于期望值。表里 64 格以内的小网格，暴力解算出的也相同。 +- 随机小网格对拍（随机种子 20261027，3000 组，$n, m \le 8$，1 的比例从 0 到 100% 分六档，包括一个 1 都没有和全是 1 的网格），正解和暴力解全部一致。 +- 全 0 网格的答案公式（见「易错点」第三条）在 $n, m$ 从 1 到 7 的 49 种尺寸上和暴力解一致。 + +两个错误写法在同一批输入上并排跑。「贪心」是把新中心放在 $d$ 最大的那个 0 上（几个 0 一样远时取行、列号最大的那个），再算不便度。「只走 4 个方向」是把正解里的 `EIGHT_DIRECTIONS` 换成上下左右，二分上界换成 $n + m$，其余不变。 + +| 输入 | 贪心放最远点 | 只走 4 个方向 | 正解 | 暴力解 | +| --- | --- | --- | --- | --- | +| `[[1,0,0,0,0,0,0]]` | 3 | 2 | 2 | 2 | +| `[[0,1,0,0],[0,0,0,0]]` | 1 | 2 | 1 | 1 | + +在上面那 3000 组随机网格上，贪心有 779 组和暴力解不同，只走 4 个方向有 413 组不同，正解 0 组。 + ## 复杂度 -- 多源 BFS 里每个格子只进队一次，是 `O(nm)`。二分最多约 `log2(500) ≈ 9` 轮，每轮判断都要扫一遍网格，也是 `O(nm)`，所以总时间是 `O(nm log max(n, m))`。空间主要是距离数组 `d`，为 `O(nm)`。 -- 在本机用 Python 跑 500×500 的三种网格（全 0、只有左上角是 1、随机 1% 的格子是 1），每种都在 1 秒以内跑完。 -- 相比之下，暴力解要对每个 0 各改一次再跑一遍 BFS，是 `O((nm)^2)`；500×500 时是 6×10^10 量级的运算，在任何合理的时限内都跑不完，只能当保底。 +多源 BFS 里每个格子只进队一次，是 $O(nm)$。二分最多约 $\log_2 500 \approx 9$ 轮，每轮判断扫一遍网格，也是 $O(nm)$。总时间 $O(nm \log \max(n, m))$，空间主要是距离数组，$O(nm)$。 + +500×500 的三种网格各跑 6 次：全 0 用 0.38 到 0.53 秒，只有左上角是 1（BFS 层数最多）用 0.79 到 0.88 秒，随机 1% 的格子是 1 用 0.48 到 0.65 秒。 + +> [!say] The BFS is O(nm) and each feasibility check is O(nm), so the total is O(nm log max(n, m)). The edge cases are a grid with no centers at all, where every cell counts as far, and a grid with no zeros, which returns 0. ## 易错点 -- 切比雪夫距离允许斜着走，所以 BFS 要往 8 个方向扩展，不是 4 个。只走 4 个方向（上下左右）算出来的是曼哈顿距离，2026-06 那位发帖人的例子就是按 4 个方向算的。 -- 网格里可以一个 1 都没有（样例 2）。所以 BFS 前要把距离初始化成无穷大，BFS 访问不到的格子保持无穷大，判断时全部算作远格子。全 0 网格的答案是 `max(n // 2, m // 2)`（3×4 → 2）。这是因为新中心放在正中间时，离它最远的格子在行方向上差行数的一半、在列方向上差列数的一半（都向下取整），切比雪夫距离取两者中较大的那个；反过来，新中心不管放在哪里，总有一个角和它在行方向上至少差 `n // 2`、在列方向上至少差 `m // 2`，所以不可能比这更小。 -- 一个容易想到的贪心（greedy）做法是把新中心放在离现有中心最远的那个 0 上，但它是错的。例如 `[[1,0,0,0,0,0,0]]`，放在最右边得到 3，而最优是放在下标 4 或 5，得到 2。原因是新中心要同时照顾所有远格子，放在最远的点上，就顾不上靠近另一侧的远格子；应该把远格子当成一个整体，放在它们包围盒的中点。 -- 题目要的是让最远的距离尽量小（min-max），别读成让最小的距离尽量小。按后一种读法，答案永远是 0 或 1：只要网格里同时有 0 和 1，总有一个 0 在 8 个方向里紧挨着某个 1，最小距离就是 1；把最后一个 0 也改成 1 的话，网格里就没有 0 了，答案是 0。这样题目就没有意义了。 -- 没有 0（全是 1）或者只有一个 0 时，答案都是 0：前者本来就没有要算距离的格子，后者把唯一那一格改掉之后也就没有了。所以二分的下界要从 0 开始。 -- 用 `float("inf")` 当无穷大也可以，但 Follow-up 里要按距离分桶，也就是拿距离当数组下标，这时用 `n + m` 这样的整数更方便。 -- 如果不放心「思路」里那一步化简，也可以按原始写法，把交集再和网格范围 `[0, n-1]`、`[0, m-1]` 求一次交，结果同样正确，只是多余，因为包围盒的中点本来就在网格里。 +- **BFS 要走 8 个方向。** 切比雪夫距离允许斜着走，只走上下左右算出来的是曼哈顿距离。距离偏大，远格子就多，答案会偏大，`[[0,1,0,0],[0,0,0,0]]` 上会算出 2，正确答案是 1（「实测」）。 +- **贪心地把新中心放在最远的 0 上是错的。** `[[1,0,0,0,0,0,0]]` 放在最右边得到 3，放在下标 4 或 5 能得到 2。新中心要同时照顾所有远格子，应该放在它们包围盒的中点（「判断一个上限是否可行」）。 +- **网格里可能一个 1 都没有**（样例 2）。距离要初始化成一个比真实距离都大的值，BFS 访问不到的格子保持这个值，判断时全部算远格子。全 0 网格的答案是 $\max(\lfloor n/2 \rfloor, \lfloor m/2 \rfloor)$，3×4 时是 2。新中心放在正中间时，最远的格子在行方向差 $\lfloor n/2 \rfloor$，列方向差 $\lfloor m/2 \rfloor$。反过来，新中心不管放哪，总有一个角在行方向离它至少 $\lfloor n/2 \rfloor$、列方向至少 $\lfloor m/2 \rfloor$，所以不可能更小。 +- **二分的下界从 0 开始。** 没有 0，或者只有一个 0（改掉之后就没有 0 了），答案都是 0。 ## 测试用例 -表里的期望值都是按切比雪夫距离算的。 +表里的期望值都按切比雪夫距离算。 | 输入 | 期望 | 说明 | @@ -134,121 +192,66 @@ | `[[0,0,0,1],[0,0,0,1]]` | 1 | 原帖样例 1 | | 3×4 全 0 | 2 | 原帖样例 2，一开始没有中心 | -| `[[1,0,0],[0,0,0],[0,0,0]]` | 1 | 站方 AI 整理，未经原帖证实 | -| `[[0,0,0,0],[0,0,0,1]]` | 1 | 2026-06 发帖人举的例子；按曼哈顿距离算是 2 | +| `[[1,0,0],[0,0,0],[0,0,0]]` | 1 | 一亩三分地站方 AI 整理区补的样例，未经原帖证实 | +| `[[0,0,0,0],[0,0,0,1]]` | 1 | 2026-06 发帖人举的例子，按曼哈顿距离算是 2 | | `[[0]]` | 0 | 改完就没有 0 了 | | `[[1]]`、`[[1,1],[1,1]]` | 0 | 没有 0 | | `[[0,0,0,0,0,0,0]]` | 3 | 单行全 0 | -| `[[1,0,0,0,0,0,0]]` | 2 | 贪心地放在最远的点上会得到 3 | -| 5×5，只有四个角是 1 | 2 | 新中心放在正中间也只能做到 2 | +| `[[1,0,0,0,0,0,0]]` | 2 | 贪心放最远点会得到 3 | +| `[[0,1,0,0],[0,0,0,0]]` | 1 | 只走 4 个方向会得到 2 | +| 5×5，只有四个角是 1 | 2 | 新中心放正中间也只能做到 2 | | 6×6，只有左上角是 1 | 3 | | | 500×500 全 0 | 250 | 规模上限 | -| 500×500，只有左上角是 1 | 250 | 规模上限，BFS 要扩展的层数最多 | +| 500×500，只有左上角是 1 | 250 | 规模上限，BFS 层数最多 | ## Follow-up -**1. 不用二分，做到 O(nm)。** 判断条件只依赖「`d > D` 的格子的包围盒」，所以可以先按 `d` 把格子分桶（bucket）：对每个距离值 k，记下距离恰好为 k 的格子的包围盒。然后让 D 从大往小走，每一步先用已经累积出来的包围盒（也就是 `d > D` 的格子）判断 D 是否可行，再把距离恰好为 D 的格子并进包围盒，留给下一个更小的 D 用。全部判断完之后，满足两边跨度都 `≤ 2D` 的最小那个 D 就是答案。距离值都不超过 `n + m`，桶的数量是 `O(n + m)`；BFS 和建桶各扫一遍网格，所以总共是 `O(nm)`。这段代码已运行过，在随机数据上和主解、暴力解对比结果（对拍），全部一致。 +**距离换成曼哈顿距离怎么做。** 2026-06 那篇帖子的例子是按曼哈顿距离算的，题面要是真这样给，要改两处。第一处是 BFS 只走 4 个方向。第二处是判断：到一个格子曼哈顿距离不超过 $D$ 的位置组成菱形，没法按行、列分别求交集。办法是换坐标 $u = x + y$、$v = x - y$，相当于把坐标系旋转 45 度并放大 $\sqrt{2}$ 倍，通常叫坐标旋转。换完之后： + +$$ +|x_1 - x_2| + |y_1 - y_2| \le D \iff |u_1 - u_2| \le D \text{ and } |v_1 - v_2| \le D +$$ + +菱形变成 $(u, v)$ 坐标下的正方形，又可以求矩形交集。要注意整数点：$u + v = 2x$，只有 $u$、$v$ 奇偶相同时才对应一个真实格子，所以矩形交集非空还不够。代码回到原坐标逐行检查：第 $r$ 行的列 $c$ 要同时满足 $u$、$v$ 的范围和 $0 \le c < m$，这一行合法列的区间非空就可行。 ```python -from collections import deque - - -def get_min_inconvenience_linear(grid): - n, m = len(grid), len(grid[0]) - INF = n + m - d = [[INF] * m for _ in range(n)] - q = deque() - for i in range(n): - for j in range(m): - if grid[i][j] == 1: - d[i][j] = 0 - q.append((i, j)) - while q: # 同上，8 方向多源 BFS - x, y = q.popleft() - for dx in (-1, 0, 1): - for dy in (-1, 0, 1): - nx, ny = x + dx, y + dy - if 0 <= nx < n and 0 <= ny < m and d[nx][ny] == INF: - d[nx][ny] = d[x][y] + 1 - q.append((nx, ny)) - # box[k]：距离恰好为 k 的格子的包围盒 [xmin, xmax, ymin, ymax] - box = [[INF, -1, INF, -1] for _ in range(INF + 1)] - for i in range(n): - for j in range(m): - b = box[d[i][j]] - b[0], b[1] = min(b[0], i), max(b[1], i) - b[2], b[3] = min(b[2], j), max(b[3], j) - # D 从大到小，累积出「d > D 的格子」的包围盒，记下每个 D 是否可行 - xmin = ymin = INF - xmax = ymax = -1 - ok = [False] * (INF + 1) - for D in range(INF, -1, -1): - ok[D] = xmax == -1 or (xmax - xmin <= 2 * D and ymax - ymin <= 2 * D) - b = box[D] - xmin, xmax = min(xmin, b[0]), max(xmax, b[1]) - ymin, ymax = min(ymin, b[2]), max(ymax, b[3]) - return ok.index(True) # 可行性单调，第一个 True 就是答案 +FOUR_DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)] + + +def can_reach_limit_manhattan(dist, limit): + n, m = len(dist), len(dist[0]) + # 旋转坐标 u = r + c, v = r - c：曼哈顿距离 <= limit 等价于 |du| <= limit 且 |dv| <= limit + u_min = v_min = n + m + u_max = v_max = -(n + m) + has_far = False + for r in range(n): + for c in range(m): + if dist[r][c] > limit: + has_far = True + u_min, u_max = min(u_min, r + c), max(u_max, r + c) + v_min, v_max = min(v_min, r - c), max(v_max, r - c) + if not has_far: + return True + u_low, u_high = u_max - limit, u_min + limit + v_low, v_high = v_max - limit, v_min + limit + # (u, v) 矩形里的点不一定对应整数格子，回到原坐标逐行找一个合法的列 + for r in range(n): + c_low = max(0, u_low - r, r - v_high) + c_high = min(m - 1, u_high - r, r - v_low) + if c_low <= c_high: + return True + return False + + +def get_min_inconvenience_manhattan(grid): + dist = nearest_center_distances(grid, FOUR_DIRECTIONS) + low, high = 0, len(grid) + len(grid[0]) + while low < high: + mid = (low + high) // 2 + if can_reach_limit_manhattan(dist, mid): + high = mid + else: + low = mid + 1 + return low ``` -**2. 如果距离换成曼哈顿距离。** 2026-06 那篇帖子的例子就是按曼哈顿距离（Manhattan distance）算的。这时 BFS 改成只走 4 个方向。判断时的难点在于：到一个格子曼哈顿距离 ≤ D 的位置组成的是菱形，不是正方形，没法像上面那样按行、列分别求交集。解决办法是把坐标换成 `u = x + y`、`v = x - y`。这个变换相当于把坐标系旋转 45 度（rotate 45 degrees）、同时放大 √2 倍，所以通常叫坐标旋转，代码注释里的「旋转坐标」说的就是这一步。换坐标之后，曼哈顿距离 ≤ D 就变成 `|du| ≤ D` 且 `|dv| ≤ D`（`du`、`dv` 是两格 `u`、`v` 坐标的差），菱形变成了 `u`、`v` 坐标下的正方形，同样是求矩形交集。要注意整数点：`u` 和 `v` 的和是 `x` 的两倍，所以只有 `u`、`v` 奇偶相同时才对应一个真实的格子。矩形交集非空还不够，要回到原坐标，逐行检查这一行有没有落在交集里的合法列。这段代码已运行过，和曼哈顿版的暴力解对拍，结果一致。 - -```python -from collections import deque - - -def get_min_inconvenience_manhattan(grid): - n, m = len(grid), len(grid[0]) - INF = n + m - d = [[INF] * m for _ in range(n)] - q = deque() - for i in range(n): - for j in range(m): - if grid[i][j] == 1: - d[i][j] = 0 - q.append((i, j)) - while q: # 曼哈顿：只走上下左右 - x, y = q.popleft() - for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)): - if 0 <= nx < n and 0 <= ny < m and d[nx][ny] == INF: - d[nx][ny] = d[x][y] + 1 - q.append((nx, ny)) - - def feasible(D): - # 旋转坐标 u = x + y, v = x - y：曼哈顿距离 ≤ D <=> |du| ≤ D 且 |dv| ≤ D - umin = vmin = 10 ** 9 - umax = vmax = -(10 ** 9) - for i in range(n): - for j in range(m): - if d[i][j] > D: - umin, umax = min(umin, i + j), max(umax, i + j) - vmin, vmax = min(vmin, i - j), max(vmax, i - j) - if umax < umin: # 没有远格子 - return True - ulo, uhi = umax - D, umin + D - vlo, vhi = vmax - D, vmin + D - # (u, v) 矩形里的点不一定对应整数格子（u、v 奇偶要相同），回原坐标逐行找 - for x in range(n): - lo = max(0, ulo - x, x - vhi) - hi = min(m - 1, uhi - x, x - vlo) - if lo <= hi: - return True - return False - - lo, hi = 0, n + m - while lo < hi: - mid = (lo + hi) // 2 - if feasible(mid): - hi = mid - else: - lo = mid + 1 - return lo -``` - -**3. 如果还要返回新中心放在哪。** 二分出答案 D 之后，再扫一遍网格，求出 `d > D` 的格子的包围盒，返回它的中点 `((xmin + xmax) // 2, (ymin + ymax) // 2)`。按「思路」第 4 条的论证，这个格子一定是 0，可以合法地改。如果没有远格子，随便挑一个 0 改就行；连 0 都没有，就不用改。这一条没写代码。 - -## 英文讲法 - -> [!say] First I run a multi-source BFS from all existing centers, moving in all eight directions, so every cell gets its Chebyshev distance to the nearest center. Then I binary-search the answer D. - -> [!say] For a candidate D, every cell that is still farther than D must be covered by the one new center, so the D-squares around those cells must intersect. I only need the min and max row and column of the far cells: D is feasible if both spans are at most 2D, and the new center goes at the middle of their bounding box. - -> [!say] BFS is O(nm) and each check is O(nm), so the total is O(nm log max(n, m)). Edge cases: a grid with no centers at all, where every cell counts as far, and a grid with no zeros, which returns 0. +判断多了逐行检查，每轮还是 $O(nm)$。二分上界换成 $n + m$（曼哈顿距离最大是 $n + m - 2$），总时间 $O(nm \log(n + m))$。2026-10-27 跑过：2026-06 那个例子算出 2，和发帖人的结果一致。在「实测」那 3000 组随机网格上和曼哈顿版暴力解对拍，结果全部一致。
meta
@@ -1 +1,5 @@ -{} +{ + "depth_guide": "2026-10-23", + "rewritten_by": "cloud:20261026-2313", + "rewritten_at": "2026-10-27" +}