leetcode
leetcode 1951 ~ 2000
统计网格图中没有被保卫的格子数

统计网格图中没有被保卫的格子数

难度:

标签:

题目描述

给你两个整数 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 <= 105
  • 2 <= m * n <= 105
  • 1 <= guards.length, walls.length <= 5 * 104
  • 2 <= guards.length + walls.length <= m * n
  • guards[i].length == walls[j].length == 2
  • 0 <= rowi, rowj < m
  • 0 <= coli, colj < n
  • guards 和 walls 中所有位置 互不相同 。

代码结果

运行时间: 274 ms, 内存: 36.6 MB

/*
 * 思路：
 * 使用Java Stream API实现同样的逻辑：
 * 1. 创建一个m x n的二维数组grid，初始化为0表示空格子。
 * 2. 将guards和walls的位置在grid中标记为2和1，表示警卫和墙。
 * 3. 对于每个警卫，向四个方向遍历，直到遇到墙或另一个警卫，将路径上的格子标记为3，表示被保卫。
 * 4. 遍历整个grid，统计没有被保卫的格子数量（值为0的格子）。
 */

import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution {
    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
        int[][] grid = new int[m][n];
        Arrays.stream(walls).forEach(wall -> grid[wall[0]][wall[1]] = 1); // 标记墙
        Arrays.stream(guards).forEach(guard -> grid[guard[0]][guard[1]] = 2); // 标记警卫
        Arrays.stream(guards).forEach(guard -> markGuarded(grid, guard[0], guard[1], m, n));
        return (int) IntStream.range(0, m).flatMap(i -> IntStream.range(0, n).filter(j -> grid[i][j] == 0)).count(); // 统计未被保卫的格子数量
    }

    private void markGuarded(int[][] grid, int x, int y, int m, int n) {
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        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) {
                if (grid[nx][ny] == 0) {
                    grid[nx][ny] = 3; // 标记为被保卫
                }
                nx += dx[d];
                ny += dy[d];
            }
        }
    }
}

解释

方法:

这道题目要求统计一个网格中未被警卫保护的格子数量。题解中采用了模拟的方式：首先，使用一个二维数组表示整个网格，初始化为0。将警卫和墙的位置分别标记为-1（警卫）和-2（墙）。然后，从每一个警卫的位置出发，向四个方向（北、南、西、东）扩展，标记所有这些警卫可以看到的格子为1，代表这些格子被保护了。此扩展在遇到另一个警卫或墙时停止。最后，计算所有未被保护的格子的数量，即网格总数减去被保护的格子数、警卫数和墙的数目。

时间复杂度:

O((guards.length * (m + n)) + m * n)

空间复杂度:

O(m * n)

代码细节讲解

🦆
在处理警卫视线扩展时，为什么没有考虑通过其他警卫的格子继续扩展视线？
▷
在算法中，警卫的视线在遇到其他警卫时停止扩展是为了避免重复处理和简化逻辑。每个警卫独立负责其可以直接观察到的区域。如果警卫的视线穿过其他警卫的位置继续扩展，将不仅增加算法的复杂度，也可能造成对同一区域的多次处理。因此，为保证效率和简洁性，警卫的视线在遇到另一个警卫时停止。
🦆
题解中提到'此扩展在遇到另一个警卫或墙时停止'，这个逻辑是基于什么考虑？是否有可能某些被其他警卫看到的格子因此没有被正确标记？
▷
此逻辑基于的考虑是，墙和其他警卫的存在形成了视线的屏障。墙体自然阻挡视线，警卫位置则是策略上的选择，即一个警卫的存在意味着其周围的区域已经或将被该警卫或其他警卫监控，避免视线穿越这些点是为了减少不必要的重复处理。此设计确保了每个格子最多被标记一次，降低了计算冗余，保证了算法的效率。如果有遗漏，通常是因为边界处理或逻辑实现错误，而不是设计本身的问题。
🦆
题解中的算法对于网格的每个方向单独进行了扩展，这种方法是否最优？是否有可能通过更高效的方式（例如使用队列）来优化视线的扩展过程？
▷
题解中使用的是直接的方向扩展方法，这种方法虽然直观但可能不是最优的，特别是在网格很大且警卫较多的情况下。可以考虑使用广度优先搜索（BFS）或深度优先搜索（DFS）来优化视线的扩展过程。例如，通过队列实现BFS可以更系统地管理和扩展每个警卫的视线，特别是处理复杂场景和多警卫交互的情况。这样的方法可能在某些情况下提高效率，尤其是在需要频繁检查和更新状态的大规模网格中。
🦆
在计算未被保卫的格子数量时，是否考虑了某些格子可能同时被多个警卫保护，而计数时重复减去这些格子？
▷
在实现中，每个格子被标记为受保护时（使用标记'1'），首次标记时会更新受保护的格子计数。即使该格子后续再次被其他警卫看到，由于已经标记为受保护，不会再次增加受保护的格子计数。这保证了即使某些格子处在多个警卫的视线范围内，它们也只被计数一次。因此，最终计算未被保卫的格子数量时，不会有重复减去的问题。

相关问题

最小平均差逃离火灾