Medium

题目描述

给你两个整数 m 和 n 表示一个下标从 0 开始的 m x n 网格图。同时给你两个二维整数数组 guards 和 walls ，其中 guards[i] = [rowi, coli] 且 walls[j] = [rowj, colj] ，分别表示第 i 个守卫和第 j 堵墙的位置。

一个守卫能够看到 4 个坐标轴方向（北，东，南，西）的 所有 格子，除非他们被一堵墙或者另外一个守卫 阻挡 了。如果一个格子能被 至少 一个守卫看到，那么我们说这个格子被 保卫 了。

请你返回空格子中，有多少个格子是 没被保卫 的。

示例 1：

输入：m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
输出：7
解释：上图中，被保卫和没有被保卫的格子分别用红色和绿色表示。
总共有 7 个没有被保卫的格子，所以我们返回 7 。

示例 2：

输入：m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
输出：4
解释：上图中，没有被保卫的格子用绿色表示。
总共有 4 个没有被保卫的格子，所以我们返回 4 。

提示：

  • 1 <= m, n <= 10^5
  • 2 <= m * n <= 10^5
  • 1 <= guards.length, walls.length <= 5 * 10^4
  • 2 <= guards.length + walls.length <= m * n
  • guards[i].length == walls[j].length == 2
  • 0 <= rowi, rowj < m
  • 0 <= coli, colj < n
  • guards 和 walls 中所有位置都是 唯一 的。

解题思路

解题思路

这道题需要模拟守卫的视线范围，统计未被保卫的空格子数量。

基本思路：

  1. 创建一个二维数组标记网格状态：0表示空格子，1表示守卫，2表示墙，3表示被保卫的格子
  2. 先标记所有守卫和墙的位置
  3. 对每个守卫，向四个方向（上下左右）扩展视线，直到遇到墙或另一个守卫为止
  4. 统计仍为0的格子数量

算法步骤：

  • 初始化网格，标记守卫和墙的位置
  • 遍历每个守卫，在四个方向上模拟视线传播
  • 对于每个方向，从守卫位置开始逐步前进，标记路径上的空格子为"被保卫"
  • 当遇到墙、守卫或边界时停止该方向的传播
  • 最后统计未被标记的格子数量

这种方法时间复杂度较优，避免了对每个格子单独判断是否被保卫的复杂计算。

代码实现

class Solution {
public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        vector<vector<int>> grid(m, vector<int>(n, 0));
        
        // 标记守卫位置
        for (auto& guard : guards) {
            grid[guard[0]][guard[1]] = 1;
        }
        
        // 标记墙位置
        for (auto& wall : walls) {
            grid[wall[0]][wall[1]] = 2;
        }
        
        // 方向数组：上、下、左、右
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        
        // 对每个守卫，向四个方向扩展视线
        for (auto& guard : guards) {
            int x = guard[0], y = guard[1];
            
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                
                while (nx >= 0 && nx < m && ny >= 0 && ny < n && 
                       grid[nx][ny] != 1 && grid[nx][ny] != 2) {
                    grid[nx][ny] = 3; // 标记为被保卫
                    nx += dx[d];
                    ny += dy[d];
                }
            }
        }
        
        // 统计未被保卫的格子
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        grid = [[0] * n for _ in range(m)]
        
        # 标记守卫位置
        for r, c in guards:
            grid[r][c] = 1
        
        # 标记墙位置
        for r, c in walls:
            grid[r][c] = 2
        
        # 方向数组：上、下、左、右
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        # 对每个守卫，向四个方向扩展视线
        for r, c in guards:
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                while 0 <= nr < m and 0 <= nc < n and grid[nr][nc] not in [1, 2]:
                    grid[nr][nc] = 3  # 标记为被保卫
                    nr += dr
                    nc += dc
        
        # 统计未被保卫的格子
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    count += 1
        
        return count

public class Solution {
    public int CountUnguarded(int m, int n, int[][] guards, int[][] walls) {
        int[,] grid = new int[m, n];
        
        // 标记守卫位置
        foreach (var guard in guards) {
            grid[guard[0], guard[1]] = 1;
        }
        
        // 标记墙位置
        foreach (var wall in walls) {
            grid[wall[0], wall[1]] = 2;
        }
        
        // 方向数组：上、下、左、右
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        
        // 对每个守卫，向四个方向扩展视线
        foreach (var guard in guards) {
            int x = guard[0], y = guard[1];
            
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                
                while (nx >= 0 && nx < m && ny >= 0 && ny < n && 
                       grid[nx, ny] != 1 && grid[nx, ny] != 2) {
                    grid[nx, ny] = 3; // 标记为被保卫
                    nx += dx[d];
                    ny += dy[d];
                }
            }
        }
        
        // 统计未被保卫的格子
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i, j] == 0) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

var countUnguarded = function(m, n, guards, walls) {
    const grid = Array(m).fill().map(() => Array(n).fill(0));
    
    // Mark walls and guards
    for (let [r, c] of walls) {
        grid[r][c] = 2; // wall
    }
    for (let [r, c] of guards) {
        grid[r][c] = 3; // guard
    }
    
    // Mark guarded cells
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    
    for (let [gr, gc] of guards) {
        for (let [dr, dc] of directions) {
            let r = gr + dr;
            let c = gc + dc;
            
            while (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] !== 2 && grid[r][c] !== 3) {
                grid[r][c] = 1; // guarded
                r += dr;
                c += dc;
            }
        }
    }
    
    // Count unguarded cells
    let count = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 0) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n + G × (m + n))，其中 G 是守卫数量。最坏情况下每个守卫需要扫描整行或整列
空间复杂度O(m × n)，用于存储网格状态

相关题目