数据结构与算法 / 系统课时

网格题怎么转成图

网格题怎么转成图

很多网格题表面上只有二维数组、障碍和上下左右移动,实际可以直接看成一张没有显式建边的图。掌握这种转换后,就能统一用 BFS 或 DFS 处理岛屿数量、区域连通、最短步数和可达性问题。

学习目标

  • 能把网格中的可通行格子、移动规则分别映射为图的顶点和边。
  • 能正确处理边界、障碍与访问标记,避免重复搜索或越界。
  • 能用隐式图上的 BFS 完成典型连通分量问题并分析复杂度。

从格子抽象为隐式图

把网格转成图时,通常不需要真的创建邻接表。只要在搜索某个格子时,根据移动规则动态计算它的邻居,就已经得到了一张隐式图。

以只能上下左右移动的二维网格为例:每个可通行格子是一个顶点;两个可通行格子上下或左右相邻时存在一条边;障碍格子可以直接视为不存在的顶点。若题目允许八方向移动,只需要增加四个对角方向即可。

网格到隐式图的映射关系

这种建模方式的关键是:位置只是顶点编号的另一种写法。普通图可能用整数 u 表示顶点,网格图则自然使用 (row, col) 表示顶点,不必额外编码成一维编号。

边界和障碍决定邻接关系

搜索一个格子时,可以先枚举方向,再检查新坐标是否合法。常用四方向可以写成 [(1, 0), (-1, 0), (0, 1), (0, -1)]。每次移动都要依次判断是否越界、是否为障碍、是否已经访问。

顺序本身不影响正确性,但三个条件缺一不可。没有边界判断会导致数组越界;没有障碍判断会穿墙;没有访问标记则可能在两个相邻格子之间反复进入,甚至让搜索无法结束。

用 BFS 验证建模

下面用“统计岛屿数量”验证这种转换。字符 1 表示陆地,0 表示水;每发现一个尚未访问的陆地,就说明找到了一个新的连通分量,再从这里执行一次 BFS 标记整座岛屿。

python
from collections import deque


def count_islands(grid: list[str]) -> int:
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    islands = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue

            # 一个未访问陆地就是一个新连通分量的起点。
            islands += 1
            seen[r][c] = True
            queue = deque([(r, c)])

            while queue:
                cr, cc = queue.popleft()
                for dr, dc in directions:
                    nr, nc = cr + dr, cc + dc
                    if not (0 <= nr < rows and 0 <= nc < cols):
                        continue
                    if grid[nr][nc] != '1' or seen[nr][nc]:
                        continue

                    # 入队时立即标记,避免同一格被多个邻居重复加入队列。
                    seen[nr][nc] = True
                    queue.append((nr, nc))

    return islands


grid = [
    '11000',
    '11000',
    '00100',
    '00011',
]
print(f'islands = {count_islands(grid)}')

预期输出

text
islands = 3

这里没有任何显式的 graph 或邻接表,但 BFS 的本质没有变化:队列中的坐标就是待访问顶点,directions 与合法性检查共同充当邻接边生成器。

复杂度和建模边界

对于 R × C 的网格,只要每个格子至多被访问一次,时间复杂度就是 O(R × C)。访问数组占用 O(R × C) 空间,BFS 队列在极端情况下也可能保存同数量级的格子。

如果题目中的“能否走到另一个格子”只依赖当前位置,那么 (row, col) 足以表示顶点;如果移动还取决于钥匙、开关、剩余次数或其他历史信息,单独使用坐标就不再完整。此时仍然是在图上搜索,只是顶点必须从“位置”扩展为包含额外信息的状态。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

网格题怎么转成图

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通