LeetCode每日一题：统计网格图中没有被保卫的格子数

Leetcode每日一题 —— 2257. 统计网格图中没有被保卫的格子数

这是一个关于计算网格中未被警卫保护的格子数的算法问题。在LeetCode上，这个问题要求我们通过给定的警卫和墙壁的位置，计算出没有被任何警卫保卫的格子数量。以下是该问题的解决思路和代码实现：

思路：
我们可以使用暴力搜索的方法，遍历每个警卫的守卫范围，将所有被警卫守卫的格子标记为已保卫，最后统计没有被标记的格子数量。由于题目没有要求优化警卫的守卫范围，我们直接按照每个方向进行直线搜索，直到遇到墙壁或边界。

代码：

private static final int DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
public int countUnguarded(int m, int n, int guards, int walls) {
    int guarded = new int[m][n];
    for (int guard : guards) {
        guarded[guard[0]][guard[1]] = -1;
    }
    for (int wall : walls) {
        guarded[wall[0]][wall[1]] = -1;
    }
    for (int guard : guards) {
        for (int dir : DIRS) {
            int x = guard[0] + dir[0], y = guard[1] + dir[1];
            int dx = dir[0], dy = dir[1];
            while (0 <= x && x < m && 0 <= y && y < n && guarded[x][y] != -1) {
                guarded[x][y] = 1;
                x += dx;
                y += dy;
            }
        }
    }
    int ans = 0;
    for (int row : guarded) {
        for (int cell : row) {
            if (cell == 0) {
                ans++;
            }
        }
    }
    return ans;
}

时间复杂度：O(mn)
空间复杂度：O(mn)

通过上述代码，我们可以有效地计算出网格中没有被警卫保护的格子数量。需要注意的是，如果警卫数量较多或者网格较大，这种方法可能会因为重复计算而变得效率低下。在实际应用中，可以考虑使用更高级的数据结构如线段树或扫描线算法来优化性能。