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

标签: 数组 矩阵 模拟

难度: 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 <= 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 中所有位置 互不相同 。

Submission

运行时间: 274 ms

内存: 36.6 MB

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        arr=[[0]*n for _ in range(m)]
        for i,j in guards:
            arr[i][j]=-1
        for i,j in walls:
            arr[i][j]=-2

        gud=0
        for i,j in guards:
            u=i-1
            d=i+1
            l=j-1
            r=j+1
            while u>=0 and arr[u][j] not in [-2,-1]:
                if arr[u][j]!=1:
                    arr[u][j]=1
                    gud+=1
                u-=1
            while l>=0 and arr[i][l] not in [-2,-1]:
                if  arr[i][l]!=1:
                    arr[i][l]=1
                    gud+=1
                l-=1
            while d<m and arr[d][j] not in [-2,-1]:
                if arr[d][j]!=1:
                    arr[d][j]=1
                    gud+=1
                d+=1

            while r<n and arr[i][r] not in [-2,-1]:
                if arr[i][r]!=1:
                    arr[i][r]=1
                    gud+=1
                r+=1
        return m*n-gud-len(guards)-len(walls)

Explain

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

时间复杂度: O((guards.length * (m + n)) + m * n)

空间复杂度: O(m * n)

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        arr=[[0]*n for _ in range(m)]  # 初始化网格
        for i,j in guards:
            arr[i][j]=-1  # 标记警卫位置
        for i,j in walls:
            arr[i][j]=-2  # 标记墙位置

        gud=0  # 用于统计被保卫的格子数量
        for i,j in guards:
            # 向四个方向扩展视线
            u=i-1
            d=i+1
            l=j-1
            r=j+1
            while u>=0 and arr[u][j] not in [-2,-1]:
                if arr[u][j]!=1:
                    arr[u][j]=1
                    gud+=1
                u-=1
            while l>=0 and arr[i][l] not in [-2,-1]:
                if arr[i][l]!=1:
                    arr[i][l]=1
                    gud+=1
                l-=1
            while d<m and arr[d][j] not in [-2,-1]:
                if arr[d][j]!=1:
                    arr[d][j]=1
                    gud+=1
                d+=1
            while r<n and arr[i][r] not in [-2,-1]:
                if arr[i][r]!=1:
                    arr[i][r]=1
                    gud+=1
                r+=1
        return m*n-gud-len(guards)-len(walls)  # 计算并返回未被保卫的格子数量

Explore

在算法中，警卫的视线在遇到其他警卫时停止扩展是为了避免重复处理和简化逻辑。每个警卫独立负责其可以直接观察到的区域。如果警卫的视线穿过其他警卫的位置继续扩展，将不仅增加算法的复杂度，也可能造成对同一区域的多次处理。因此，为保证效率和简洁性，警卫的视线在遇到另一个警卫时停止。

此逻辑基于的考虑是，墙和其他警卫的存在形成了视线的屏障。墙体自然阻挡视线，警卫位置则是策略上的选择，即一个警卫的存在意味着其周围的区域已经或将被该警卫或其他警卫监控，避免视线穿越这些点是为了减少不必要的重复处理。此设计确保了每个格子最多被标记一次，降低了计算冗余，保证了算法的效率。如果有遗漏，通常是因为边界处理或逻辑实现错误，而不是设计本身的问题。

题解中使用的是直接的方向扩展方法，这种方法虽然直观但可能不是最优的，特别是在网格很大且警卫较多的情况下。可以考虑使用广度优先搜索（BFS）或深度优先搜索（DFS）来优化视线的扩展过程。例如，通过队列实现BFS可以更系统地管理和扩展每个警卫的视线，特别是处理复杂场景和多警卫交互的情况。这样的方法可能在某些情况下提高效率，尤其是在需要频繁检查和更新状态的大规模网格中。

在实现中，每个格子被标记为受保护时（使用标记'1'），首次标记时会更新受保护的格子计数。即使该格子后续再次被其他警卫看到，由于已经标记为受保护，不会再次增加受保护的格子计数。这保证了即使某些格子处在多个警卫的视线范围内，它们也只被计数一次。因此，最终计算未被保卫的格子数量时，不会有重复减去的问题。