Hard

题目描述

病毒正在迅速传播，你的任务是通过建造防护墙来隔离感染区域。

世界被建模为一个 m x n 的二进制网格 isInfected，其中 isInfected[i][j] == 0 表示未感染的细胞，isInfected[i][j] == 1 表示被病毒感染的细胞。可以在任何两个 4 方向相邻的细胞之间的共享边界上安装一堵墙（且只能安装一堵墙）。

每晚，病毒都会向所有四个方向的相邻细胞传播，除非被墙阻挡。资源有限。每天，你只能围绕一个区域安装墙壁（即，威胁第二天晚上最多未感染细胞的受影响区域（感染细胞的连续块））。永远不会有平局。

返回隔离所有感染区域所用的墙壁数量。如果世界将完全被感染，返回所使用的墙壁数量。

示例 1：

输入：isInfected = [[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0]]
输出：10
解释：有 2 个受感染的区域。
第一天，添加 5 堵墙来隔离左边的病毒区域。病毒传播后的板子是：
第二天，添加 5 堵墙来隔离右边的病毒区域。病毒完全被控制住了。

示例 2：

输入：isInfected = [[1,1,1],[1,0,1],[1,1,1]]
输出：4
解释：即使只拯救了一个细胞，也建造了 4 堵墙。
请注意，墙只建在两个不同细胞的共享边界上。

示例 3：

输入：isInfected = [[1,1,1,0,0,0,0,0,0],[1,0,1,0,1,1,1,1,1],[1,1,1,0,0,0,0,0,0]]
输出：13
解释：左边的区域只建造了两堵新墙。

提示：

  • m == isInfected.length
  • n == isInfected[i].length
  • 1 <= m, n <= 50
  • isInfected[i][j] 不是 0 就是 1
  • 在所描述的过程中，总是有一个连续的病毒区域，它将在下一轮中感染严格更多的未污染方块。

解题思路

这道题是一个模拟题，需要按照题目描述的规则逐步执行：

解题思路

核心策略： 每天找到威胁最多未感染细胞的病毒区域，对其建墙隔离，然后让其他区域扩散一轮。

算法步骤：

  1. 找到所有病毒区域： 使用 DFS/BFS 找到所有连通的感染区域
  2. 计算威胁度： 对每个区域，计算其边界能感染的未感染细胞数量
  3. 选择最危险区域： 找到威胁度最高的区域进行隔离
  4. 建墙隔离： 计算需要的墙数（即该区域的周长），将该区域标记为已隔离
  5. 病毒扩散： 其他未隔离的区域向外扩散一格
  6. 重复以上过程： 直到没有病毒区域或所有区域都被隔离

技术细节：

  • 使用 DFS 遍历连通区域，同时记录边界细胞和所需墙数
  • 威胁度 = 该区域边界能感染的不重复的未感染细胞数
  • 已隔离的区域标记为 -1，不再扩散
  • 需要特别注意边界计算，每个感染细胞与未感染邻居之间需要一堵墙

这是一道考查图遍历、模拟和细节处理的综合题目，需要仔细实现每个步骤。

代码实现

class Solution {
public:
    int containVirus(vector<vector<int>>& isInfected) {
        int m = isInfected.size(), n = isInfected[0].size();
        int totalWalls = 0;
        vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (true) {
            vector<vector<bool>> visited(m, vector<bool>(n, false));
            vector<vector<pair<int, int>>> regions; // 所有病毒区域
            vector<set<pair<int, int>>> frontiers; // 每个区域的边界
            vector<int> wallCounts; // 每个区域需要的墙数
            
            // 找到所有病毒区域
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (isInfected[i][j] == 1 && !visited[i][j]) {
                        vector<pair<int, int>> region;
                        set<pair<int, int>> frontier;
                        int walls = 0;
                        dfs(isInfected, i, j, visited, region, frontier, walls, directions);
                        if (!frontier.empty()) {
                            regions.push_back(region);
                            frontiers.push_back(frontier);
                            wallCounts.push_back(walls);
                        }
                    }
                }
            }
            
            if (regions.empty()) break;
            
            // 找到威胁最大的区域
            int maxThreat = 0, maxIdx = 0;
            for (int i = 0; i < frontiers.size(); i++) {
                if (frontiers[i].size() > maxThreat) {
                    maxThreat = frontiers[i].size();
                    maxIdx = i;
                }
            }
            
            // 隔离威胁最大的区域
            totalWalls += wallCounts[maxIdx];
            for (auto& cell : regions[maxIdx]) {
                isInfected[cell.first][cell.second] = -1; // 标记为已隔离
            }
            
            // 其他区域扩散
            for (int i = 0; i < regions.size(); i++) {
                if (i != maxIdx) {
                    for (auto& cell : frontiers[i]) {
                        isInfected[cell.first][cell.second] = 1;
                    }
                }
            }
        }
        
        return totalWalls;
    }
    
private:
    void dfs(vector<vector<int>>& isInfected, int x, int y, vector<vector<bool>>& visited,
             vector<pair<int, int>>& region, set<pair<int, int>>& frontier, int& walls,
             vector<vector<int>>& directions) {
        int m = isInfected.size(), n = isInfected[0].size();
        visited[x][y] = true;
        region.push_back({x, y});
        
        for (auto& dir : directions) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                if (isInfected[nx][ny] == 0) {
                    frontier.insert({nx, ny});
                    walls++;
                } else if (isInfected[nx][ny] == 1 && !visited[nx][ny]) {
                    dfs(isInfected, nx, ny, visited, region, frontier, walls, directions);
                }
            }
        }
    }
};

class Solution:
    def containVirus(self, isInfected: List[List[int]]) -> int:
        m, n = len(isInfected), len(isInfected[0])
        total_walls = 0
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        def dfs(x, y, visited, region, frontier, walls):
            visited[x][y] = True
            region.append((x, y))
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n:
                    if isInfected[nx][ny] == 0:
                        frontier.add((nx, ny))
                        walls[0] += 1
                    elif isInfected[nx][ny] == 1 and not visited[nx][ny]:
                        dfs(nx, ny, visited, region, frontier, walls)
        
        while True:
            visited = [[False] * n for _ in range(m)]
            regions = []
            frontiers = []
            wall_counts = []
            
            # 找到所有病毒区域
            for i in range(m):
                for j in range(n):
                    if isInfected[i][j] == 1 and not visited[i][j]:
                        region = []
                        frontier = set()
                        walls = [0]
                        dfs(i, j, visited, region, frontier, walls)
                        if frontier:
                            regions.append(region)
                            frontiers.append(frontier)
                            wall_counts.append(walls[0])
            
            if not regions:
                break
            
            # 找到威胁最大的区域
            max_threat = max(len(frontier) for frontier in frontiers)
            max_idx = next(i for i, frontier in enumerate(frontiers) if len(frontier) == max_threat)
            
            # 隔离威胁最大的区域
            total_walls += wall_counts[max_idx]
            for x, y in regions[max_idx]:
                isInfected[x][y] = -1
            
            # 其他区域扩散
            for i, frontier in enumerate(frontiers):
                if i != max_idx:
                    for x, y in frontier:
                        isInfected[x][y] = 1
        
        return total_walls

public class Solution {
    public int ContainVirus(int[][] isInfected) {
        int m = isInfected.Length, n = isInfected[0].Length;
        int totalWalls = 0;
        int[,] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (true) {
            bool[,] visited = new bool[m, n];
            List<List<(int, int)>> regions = new List<List<(int, int)>>();
            List<HashSet<(int, int)>> frontiers = new List<HashSet<(int, int)>>();
            List<int> wallCounts = new List<int>();
            
            // 找到所有病毒区域
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (isInfected[i][j] == 1 && !visited[i, j]) {
                        var region = new List<(int, int)>();
                        var frontier = new HashSet<(int, int)>();
                        int walls = 0;
                        DFS(isInfected, i, j, visited, region, frontier, ref walls, directions);
                        if (frontier.Count > 0) {
                            regions.Add(region);
                            frontiers.Add(frontier);
                            wallCounts.Add(walls);
                        }
                    }
                }
            }
            
            if (regions.Count == 0) break;
            
            // 找到威胁最大的区域
            int maxThreat = 0, maxIdx = 0;
            for (int i = 0; i < frontiers.Count; i++) {
                if (frontiers[i].Count > maxThreat) {
                    maxThreat = frontiers[i].Count;
                    maxIdx = i;
                }
            }
            
            // 隔离威胁最大的区域
            totalWalls += wallCounts[maxIdx];
            foreach (var cell in regions[maxIdx]) {
                isInfected[cell.Item1][cell.Item2] = -1;
            }
            
            // 其他区域扩散
            for (int i = 0; i < regions.Count; i++) {
                if (i != maxIdx) {
                    foreach (var cell in frontiers[i]) {
                        isInfected[cell.Item1][cell.Item2] = 1;
                    }
                }
            }
        }
        
        return totalWalls;
    }
    
    private void DFS(int[][] isInfected, int x, int y, bool[,] visited,
                     List<(int, int)> region, HashSet<(int, int)> frontier, 
                     ref int walls, int[,] directions) {
        int m = isInfected.Length, n = isInfected[0].Length;
        visited[x, y] = true;
        region.Add((x, y));
        
        for (int d = 0; d < 4; d++) {
            int nx = x + directions[d, 0], ny = y + directions[d, 1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                if (isInfected[nx][ny] == 0) {
                    frontier.Add((nx, ny));
                    walls++;
                } else if (isInfected[nx][ny] == 1 && !visited[nx, ny]) {
                    DFS(isInfected, nx, ny, visited, region, frontier, ref walls, directions);
                }
            }
        }
    }
}

var containVirus = function(isInfected) {
    const m = isInfected.length;
    const n = isInfected[0].length;
    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    let totalWalls = 0;
    
    while (true) {
        const visited = Array.from({length: m}, () => Array(n).fill(false));
        const regions = [];
        
        // Find all infected regions
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (isInfected[i][j] === 1 && !visited[i][j]) {
                    const region = {
                        cells: [],
                        threatened: new Set(),
                        walls: 0
                    };
                    
                    const dfs = (r, c) => {
                        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || isInfected[r][c] !== 1) {
                            return;
                        }
                        
                        visited[r][c] = true;
                        region.cells.push([r, c]);
                        
                        for (const [dr, dc] of dirs) {
                            const nr = r + dr;
                            const nc = c + dc;
                            
                            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                                if (isInfected[nr][nc] === 0) {
                                    region.threatened.add(nr * n + nc);
                                    region.walls++;
                                } else if (isInfected[nr][nc] === 1 && !visited[nr][nc]) {
                                    dfs(nr, nc);
                                }
                            }
                        }
                    };
                    
                    dfs(i, j);
                    regions.push(region);
                }
            }
        }
        
        if (regions.length === 0) break;
        
        // Find region that threatens most cells
        let maxThreatened = -1;
        let quarantineIdx = -1;
        
        for (let i = 0; i < regions.length; i++) {
            if (regions[i].threatened.size > maxThreatened) {
                maxThreatened = regions[i].threatened.size;
                quarantineIdx = i;
            }
        }
        
        if (maxThreatened === 0) break;
        
        // Quarantine the most threatening region
        totalWalls += regions[quarantineIdx].walls;
        
        for (const [r, c] of regions[quarantineIdx].cells) {
            isInfected[r][c] = -1; // Mark as quarantined
        }
        
        // Spread other regions
        for (let i = 0; i < regions.length; i++) {
            if (i === quarantineIdx) continue;
            
            for (const pos of regions[i].threatened) {
                const r = Math.floor(pos / n);
                const c = pos % n;
                isInfected[r][c] = 1;
            }
        }
    }
    
    return totalWalls;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(k × m × n)，其中 k 是模拟的轮数，最坏情况下为 O(m × n)，每轮需要遍历整个网格
空间复杂度O(m × n)，用于存储访问标记、区域信息和边界信息

相关题目