如何在网格中寻找‘湖泊’（被包围的0）？

嘿，这个问题我之前也碰到过！其实核心就是要区分和网格边缘连通的海洋（0），以及被陆地（1）完全包围的湖泊（0），用BFS或者DFS就能轻松解决，我给你拆解一下具体步骤：

核心思路 #

湖泊的关键特征是：完全被陆地包裹，不会和网格边界的水域连通。所以我们可以先把所有和边界连通的水域标记出来，剩下的未被标记的水域就是我们要找的湖泊了。

具体步骤 #

第一步：标记所有连通到边缘的海洋 #

遍历网格的四条边界（第一行、最后一行、第一列、最后一列），只要遇到值为0的单元格，就用BFS或者DFS遍历所有和它连通的0，把这些单元格标记为非湖泊（比如改成2，或者其他和0、1不同的数值）。这些就是和外界海洋连通的水域，排除在湖泊之外。

第二步：识别剩余的湖泊 #

处理完边界连通的水域后，网格里剩下的0就是被陆地包围的湖泊了。这时候你可以遍历整个网格，统计这些0的数量，或者给它们做特殊标记来区分。

代码示例（Python BFS实现） #

def count_lakes(grid):
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    from collections import deque
    
    # 用BFS标记所有连通到边缘的海洋
    def bfs_mark_ocean(r, c):
        queue = deque()
        queue.append((r, c))
        grid[r][c] = 2  # 标记为海洋，避免重复处理
        # 上下左右四个方向
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while queue:
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                # 检查是否在网格范围内，且是未标记的水域
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0:
                    grid[nx][ny] = 2
                    queue.append((nx, ny))
    
    # 遍历四条边界，标记连通的海洋
    for i in range(rows):
        if grid[i][0] == 0:
            bfs_mark_ocean(i, 0)
        if grid[i][cols - 1] == 0:
            bfs_mark_ocean(i, cols - 1)
    for j in range(cols):
        if grid[0][j] == 0:
            bfs_mark_ocean(0, j)
        if grid[rows - 1][j] == 0:
            bfs_mark_ocean(rows - 1, j)
    
    # 统计湖泊的数量（剩余的0就是湖泊）
    lake_count = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 0:
                lake_count += 1
                # 如果需要标记湖泊位置，可以在这里再跑一次BFS把0改成3之类的
                # bfs_mark_lake(i, j)
    return lake_count

额外小贴士 #

• 你也可以用DFS代替BFS，逻辑完全一致，只是把队列换成栈（或者递归调用）就行。不过如果网格特别大，递归DFS可能会遇到栈溢出的问题，这时候BFS更稳妥。
• 如果不想修改原始网格，可以先复制一份再进行标记操作，避免破坏原数据。
• 针对你给出的两个例子：第一个例子中间的0完全被1包围，处理后会保留为0，被统计为湖泊；第二个例子右边的0和网格边缘连通，会被标记为2，不会被算作湖泊。

内容的提问来源于stack exchange，提问作者Michael