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