Saturday, March 24, 2018

[LeetCode]Contain Virus

照着题目的描述来做就行。每一次扫一遍矩阵找出所有被感染的region,和对应的边界。然后每次找出下一天可以感染最多cell的区域,将其隔离。一直重复直到我们隔离所有感染区域或者整个世界被感染位置。具体细节:

  1. 边界我们应该存什么?是把区域围起来的0,还是在和0相邻的1?这里我们仔细想一下就很好理解,我们显然应该存0,因为每一次我们要找的是下一天周围会被感染最多的region,那就是对应周围的0。1的话并不能准确表示,比如题目给出的例子:

    如果我们只记录1的话,边界的size会变成4。记录0的话可以正确反映下一轮会被感染的cells的多少。
  2. 我们要建的墙的数量和边界的数量并不是一样的,比如下图:     
     蓝色的部分代表我们维护的边界,红色的部分代表我们要建的墙。我们可以看到数量分别为5和7,所以边界和墙我们要分别统计。统计墙的话,我们只要知道如果我们可以从value为1的任意一个方向到达value为0的cell,我们就需要建一堵墙。
假设输入矩阵大小为r * c,空间复杂度O(r * c),时间复杂度最坏O(r^2 * c^2),我们每次最多扫两次矩阵,迭代次数不会超过r * c次。代码如下:


No comments:

Post a Comment