LeetCode 每日一题笔记

0. 前言

• 日期：2025.11.02
• 题目：2257. 统计未被Guard捕获的格子
• 难度：中等
• 标签: 数组, 矩阵, 模拟

1. 题目理解

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

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

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

示例：

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

2. 解题思路

核心观察

• 警卫的视野是四个方向（东、南、西、北）的直线延伸，直到被墙或其他警卫阻挡。
• 我们可以通过模拟每个警卫的视野，标记出所有被保卫的格子，最后统计未被标记的空格子数量。

算法步骤

1. 初始化网格：用一个二维数组 grid 记录每个格子的状态（0：未被保卫的空格；1：警卫；2：墙；3：被保卫的空格）。
2. 标记警卫和墙：先将所有警卫和墙的位置分别标记为 1 和 2。
3. 模拟警卫视野：对每个警卫，向四个方向遍历，沿途标记所有能看到的空格子为 3（被保卫），直到遇到墙或其他警卫时停止。
4. 统计结果：遍历整个网格，统计值为 0 的格子数量（即未被保卫的空格子）。

3. 代码实现

class lc3600_lc3699.lc3660.Solution {
    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
        int[][] grid = new int[m][n];
        // 标记警卫位置
        for (int[] g : guards) {
            int r = g[0], c = g[1];
            grid[r][c] = 1;
        }
        // 标记墙的位置
        for (int[] w : walls) {
            int r = w[0], c = w[1];
            grid[r][c] = 2;
        }
        // 四个方向：北、东、南、西
        int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        // 遍历每个警卫，模拟其视野
        for (int[] g : guards) {
            int r = g[0], c = g[1];
            for (int[] d : dirs) {
                int nr = r + d[0];
                int nc = c + d[1];
                while (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    if (grid[nr][nc] == 1 || grid[nr][nc] == 2) {
                        break; // 遇到警卫或墙，停止当前方向遍历
                    }
                    grid[nr][nc] = 3; // 标记为被保卫的空格
                    nr += d[0];
                    nc += d[1];
                }
            }
        }
        // 统计未被保卫的空格子数
        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;
    }
}

4. 代码优化说明

• 可以将“警卫”和“墙”的标记合并为同一类（如都标记为 1），减少状态判断，使代码更简洁（但需注意逻辑一致性）。
• 遍历方向时，可通过合并循环条件（如 grid[nr][nc] == 0）来简化判断，提升代码可读性。

5. 复杂度分析

• 时间复杂度：( O(m \times n + G \times (m + n) + W) )，其中 ( G ) 是警卫数量，( W ) 是墙的数量。初始化网格为 ( O(m \times n) )，每个警卫最多向四个方向遍历 ( O(m + n) ) 个格子，标记墙为 ( O(W) )。
• 空间复杂度：( O(m \times n) )，用于存储网格状态数组。

6. 总结

本题的核心是模拟警卫的直线视野，通过状态标记法清晰地区分“警卫、墙、被保卫的空格、未被保卫的空格”。这种“模拟 + 统计”的思路在矩阵类问题中很常见，关键在于准确处理边界和阻挡条件。通过合理的状态设计和方向遍历，可高效解决此类网格模拟问题。