algorithm - 算法问题：在二维网格中查找与某些特定单元格距离为 K 的所有单元格

Question

我一直在思考一个问题，但找不到有效的算法。它类似于这个问题。我有一个二维网格，一些单元格为 1，其他单元格为 0。现在我需要找到与所有其他 1 个单元格的距离不超过 K 的所有 0 个单元格。那么有多少个符合条件的单元格呢？我知道蛮力，对于每个零单元格检查所有其他 1 个单元格。如果 n^2 /2 为 0 且 n^2/2 为 1，则时间复杂度为 O(n^4)。但它不是最好的算法（它不是硬件或项目只是我无法解决的 ACM 问题）
0 0 0 1
0 0 0 0
0 0 1 0
0 0 0 0

如果 K =2 则
0 0 X 1
0 0 XX
0 0 1 X
0 0 0 0

标签： algorithmgraphdynamic-programmingrecursive-datastructures