LeetCode #200：岛屿数量

1970-01-01 00:00 (GMT+8) 阅读时间 0 分钟 LeetCodeLeetCode-MediumDFSBFS泛洪填充并查集数组矩阵

https://leetcode.cn/problems/number-of-islands/description/

题目分析

找到一个很巧妙的评论：

很简单，制作一张bool的二位数组用来记录“陆海情况” 现在引入新机制：放火。火焰会烧焦陆地，同时流窜到上下左右未烧焦的陆地。陆地被烧焦就在bool地图上标记一下。 遍历地图地块，如果是未烧焦的陆地，就在此地放火直到火焰完全扩散。 最终统计放了多少把火即可

这是一个很巧妙的思路，实际上叫泛洪填充，可以用 BFS 或者 DFS 实现。我自己用的是 DFS（因为 DFS 不怎么需要脑子），也让 ChatGPT 实现了一版 BFS 的，以备面试官的 follow up。

题解

BFS (Python)

class Solution:
    def __init__(self):
        self.flood_count = 0

    def flood(self, x, y, grid):
        m, n = len(grid), len(grid[0])  # get grid size
        if (
            x < 0 or y < 0 or x >= m or y >= n or grid[x][y] is not "1"
        ):  # if out of bound or is not land
            return
        # if is land:
        grid[x][y] = "0"  # mark current as flooded
        # spread
        self.flood(x - 1, y, grid)
        self.flood(x, y + 1, grid)
        self.flood(x + 1, y, grid)
        self.flood(x, y - 1, grid)

    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:  # empty map
            return
        self.flood_count = 0

        m, n = len(grid), len(grid[0])  # get grid size
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    self.flood_count += 1
                    self.flood(i, j, grid)

        return self.flood_count

DFS (Python)

from collections import deque
from typing import List

class Solution:
    def __init__(self):
        self.flood_count = 0

    # BFS 泛洪：从 (start_x, start_y) 开始，用队列按层扩散
    def flood(self, start_x: int, start_y: int, grid: List[List[str]]) -> None:
        m, n = len(grid), len(grid[0])
        q = deque()
        q.append((start_x, start_y))
        grid[start_x][start_y] = '0'          # 先把起点标记为已烧焦

        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 < m and 0 <= ny < n and grid[nx][ny] == '1':
                    grid[nx][ny] = '0'
                    q.append((nx, ny))

    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        self.flood_count = 0
        m, n = len(grid), len(grid[0])

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    self.flood_count += 1   # 点一把“火”
                    self.flood(i, j, grid) # BFS 把整座岛烧完

        return self.flood_count

页面历史

最后编辑于 6 天前

查看完整历史

0a35851-docs: 添加 LeetCode #200 - 岛屿数量 题解