309魔幻世界中的安全区计算

题解

问题分析

在一个大小为 n x m 的二维数组中，每个格子的值表示该位置的危险程度。小 F 的能力值为 X，当某个格子的危险程度小于等于 X 时，该格子被认为是安全的。相邻（上下左右连通）的安全格子组成一个安全区。需要计算整个二维数组中有多少个安全区。

解题思路

这题本质就是计算连通块的数量。使用广度优先搜索（BFS）遍历二维数组，标记已访问的安全格子。对于每一个未访问且安全的格子，启动一次 BFS，将所有相连的安全格子标记为已访问，并将安全区计数加一。

代码解析

from collections import deque
def solution(n: int, m: int, X: int, a: list[list[int]]) -> int:
    vis = [[0] * m for _ in range(n)]
    def bfs(x, y):
        q = deque([(x, y)])
        vis[x][y] = 1
        while q:
            x, y = q.popleft()
            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and not vis[nx][ny] and a[nx][ny] <= X:
                    vis[nx][ny] = 1
                    q.append((nx, ny))
        return 1
    res = sum(bfs(i, j) for i in range(n) for j in range(m) if not vis[i][j] and a[i][j] <= X)
    return res



if __name__ == '__main__':
    print(solution(3, 3, 4, [[2, 3, 3], [3, 3, 3], [3, 3, 3]]) == 1)
    print(solution(2, 2, 5, [[6, 6], [6, 4]]) == 1)
    print(solution(3, 3, 3, [[1, 2, 2], [2, 3, 3], [3, 4, 5]]) == 1)

复杂度分析

时间复杂度:通过 BFS 方法遍历整个二维数组，每个格子最多只被遍历一次，所以时间复杂度为 O(n * m)。
空间复杂度:空间复杂度 O(n * m)。