0749. Contain Virus¶
题目信息¶
- 题号:
0749
- 难度:
Hard
- 主题:
矩阵、连通区域、传播模拟
- 原题:
- 重点:
每天只能隔离一个四方向连通感染区,必须选择下一夜威胁未感染格子数最多且答案保证唯一的区域;墙按感染格与未感染邻格之间的共享边计数
题目重述¶
给定 m x n 二进制矩阵 isInfected。值 1 表示感染格子,值 0 表示未感染格子;只通过上、下、左、右相邻关系形成感染区域和传播路径。墙只能建在两个四方向相邻格子的共享边上。
每天白天,找出当前所有感染区域中,若不阻挡将在当晚感染最多不同未感染格子的区域。题目保证需要选择时该区域唯一。沿这个区域与所有相邻未感染格子之间的每一条共享边建墙,使该区域被永久隔离;同一个未感染格子若与区域内多个感染格相邻,可能需要多面墙。
当晚,除已隔离区域外,其余感染区域会向所有没有墙阻挡的四方向相邻未感染格子传播。重复这一过程,直到病毒无法继续传播;若最终整个世界都会被感染,也在过程停止时返回。结果是整个过程中建造的墙的总数。
1 <= m, n <= 50,矩阵元素只可能为 0 或 1。题目保证在每个仍需处理的阶段,都有唯一一个感染区域将在下一轮威胁严格最多的未感染格子。
自建示例¶
单个感染格位于中心:
输入:isInfected = [[0,0,0],[0,1,0],[0,0,0]]
输出:4
解释:中心感染格与上、下、左、右四个未感染格各共享一条边,需要建 4 面墙即可完全隔离,之后不再传播。
边界上的感染区域只计算网格内部共享边:
输入:isInfected = [[1,1,0,0]]
输出:1
解释:感染区域只会通过第二个格子与第三个格子的共享边向右传播,因此建 1 面墙即可隔离;网格外侧不需要建墙。