- 边界我们应该存什么?是把区域围起来的0,还是在和0相邻的1?这里我们仔细想一下就很好理解,我们显然应该存0,因为每一次我们要找的是下一天周围会被感染最多的region,那就是对应周围的0。1的话并不能准确表示,比如题目给出的例子:
- 我们要建的墙的数量和边界的数量并不是一样的,比如下图: 蓝色的部分代表我们维护的边界,红色的部分代表我们要建的墙。我们可以看到数量分别为5和7,所以边界和墙我们要分别统计。统计墙的话,我们只要知道如果我们可以从value为1的任意一个方向到达value为0的cell,我们就需要建一堵墙。
假设输入矩阵大小为r * c,空间复杂度O(r * c),时间复杂度最坏O(r^2 * c^2),我们每次最多扫两次矩阵,迭代次数不会超过r * c次。代码如下:
No comments:
Post a Comment