求2D网格中与所有1单元格距离不超过K的0单元格数量的高效算法

该问题可以在 O(nm) 时间复杂度下求解（n、m分别为网格的行数和列数），核心利用曼哈顿距离的坐标变换特性结合二维差分，规避暴力校验的高耗时问题。

核心原理 #

题目要求0单元格与所有1的曼哈顿距离均不超过K，等价于：该单元格被所有1对应的「曼哈顿距离≤K的菱形覆盖区域」共同覆盖。我们只需要统计每个单元格被覆盖的次数，若次数等于1的总个数且原单元格值为0，即为符合要求的单元格。

坐标变换简化操作 #

对于任意1的坐标(a,b)，满足曼哈顿距离|x-a| + |y-b| ≤ K的(x,y)可以通过坐标转换变为切比雪夫距离下的矩形约束：
令u = x + y，v = x - y，则原约束等价为：

a + b - K ≤ u ≤ a + b + K
a - b - K ≤ v ≤ a - b + K

此时原本的菱形区域覆盖操作就转换为uv坐标系下的矩形区间加1操作，仅需用二维差分数组就能在O(1)时间内完成单个1的区域标记。

具体实现步骤 #

• 遍历原始网格，统计所有1的坐标，记录1的总个数S
• 初始化uv坐标系下的差分数组diff，根据u、v的取值范围设置偏移量（v的取值可能为负，加偏移量后可转为非负索引方便数组操作）
• 对每个1的坐标(a,b)，执行差分数组的矩形加1操作，注意要将u、v的边界限制在网格合法范围内：

  int u1 = max(0, a + b - K), u2 = min(n + m - 2, a + b + K);
  int v1 = max(-(m-1), a - b - K), v2 = min(n-1, a - b + K);
  // 差分数组更新，offset取值为m-1将v转为非负索引
  diff[u1][v1 + offset] += 1;
  diff[u1][v2 + 1 + offset] -= 1;
  diff[u2 + 1][v1 + offset] -= 1;
  diff[u2 + 1][v2 + 1 + offset] += 1;
  

• 对差分数组做二维前缀和计算，得到每个(u,v)对应的覆盖次数，再映射回原网格的(x,y)坐标，得到原网格每个位置的覆盖次数cnt[x][y]
• 遍历原网格，统计所有满足grid[x][y] == 0且cnt[x][y] == S的单元格总数即可

简易替代方案 #

如果网格规模很小或者1的数量极少，也可以采用逐1 BFS的方案实现：对每个1跑一次BFS得到全网格到该1的距离，维护每个单元格的最大距离，最后遍历统计最大距离≤K的0单元格即可，代码实现更简单。

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