求网格中与所有果树曼哈顿距离≤k的空地点数的高效算法

直接利用曼哈顿距离的性质做线性时间求解，时间复杂度仅为O(mn)（m为网格行数，n为网格列数），完全不受果树数量、k值大小影响。

核心原理 #

两个点(x1,y1)、(x2,y2)的曼哈顿距离|x1-x2| + |y1-y2|可以等价变形为以下四个表达式的最大值：

• (x1 + y1) - (x2 + y2)
• (x2 + y2) - (x1 + y1)
• (x1 - y1) - (x2 - y2)
• (x2 - y2) - (x1 - y1)

要求空位(x,y)到所有果树的曼哈顿距离都≤k，等价于同时满足以下四个条件：

1. 对所有果树(xi, yi)，(x + y) - (xi + yi) ≤k → 仅需保证(x+y) - 所有果树(xi+yi)的最小值 ≤k即可（因为xi+yi越小，左边值越大）
2. 对所有果树(xi, yi)，(xi + yi) - (x + y) ≤k → 仅需保证所有果树(xi+yi)的最大值 - (x+y) ≤k即可（因为xi+yi越大，左边值越大）
3. 对所有果树(xi, yi)，(x - y) - (xi - yi) ≤k → 仅需保证(x-y) - 所有果树(xi-yi)的最小值 ≤k即可
4. 对所有果树(xi, yi)，(xi - yi) - (x - y) ≤k → 仅需保证所有果树(xi-yi)的最大值 - (x-y) ≤k即可

算法步骤 #

1. 第一次遍历整个网格，收集所有果树的位置，同时计算四个极值：
   • max_s：所有果树xi + yi的最大值
   • min_s：所有果树xi + yi的最小值
   • max_d：所有果树xi - yi的最大值
   • min_d：所有果树xi - yi的最小值

   如果网格中没有果树，按题目要求处理边界情况即可

2. 第二次遍历整个网格，对每个空位（值为0的单元格），代入上述四个条件判断，全部满足则计入结果
3. 返回总计数即可

正确性验证 #

用你给出的反例验证：
k=4，三个果树的坐标分别为(0,3)、(1,1)、(3,0)
计算四个极值：

• max_s = max(0+3,1+1,3+0) = 3
• min_s = min(3,2,3) = 2
• max_d = max(0-3,1-1,3-0) = 3
• min_d = min(-3,0,3) = -3

右下角空位坐标为(4,3)：
x+y=7，x-y=1
四个条件判断：
7 - min_s = 7-2=5>4 → 不满足，直接排除，和实际计算的距离5>4结果一致。

和你给出的第一个示例也完全匹配，计算结果为2，符合预期。

复杂度说明 #

仅需两次遍历网格，不需要做多次BFS或者集合交集运算，即使是1e3 * 1e3规模的网格也可以在毫秒级完成计算，比原有方案性能提升几个数量级。

内容的提问来源于stack exchange，提问作者CaTs