数据结构与算法 / 系统课时
网格题怎么转成图
网格题怎么转成图
很多网格题表面上只有二维数组、障碍和上下左右移动,实际可以直接看成一张没有显式建边的图。掌握这种转换后,就能统一用 BFS 或 DFS 处理岛屿数量、区域连通、最短步数和可达性问题。
学习目标
- 能把网格中的可通行格子、移动规则分别映射为图的顶点和边。
- 能正确处理边界、障碍与访问标记,避免重复搜索或越界。
- 能用隐式图上的 BFS 完成典型连通分量问题并分析复杂度。
从格子抽象为隐式图
把网格转成图时,通常不需要真的创建邻接表。只要在搜索某个格子时,根据移动规则动态计算它的邻居,就已经得到了一张隐式图。
以只能上下左右移动的二维网格为例:每个可通行格子是一个顶点;两个可通行格子上下或左右相邻时存在一条边;障碍格子可以直接视为不存在的顶点。若题目允许八方向移动,只需要增加四个对角方向即可。

这种建模方式的关键是:位置只是顶点编号的另一种写法。普通图可能用整数 u 表示顶点,网格图则自然使用 (row, col) 表示顶点,不必额外编码成一维编号。
边界和障碍决定邻接关系
搜索一个格子时,可以先枚举方向,再检查新坐标是否合法。常用四方向可以写成 [(1, 0), (-1, 0), (0, 1), (0, -1)]。每次移动都要依次判断是否越界、是否为障碍、是否已经访问。
顺序本身不影响正确性,但三个条件缺一不可。没有边界判断会导致数组越界;没有障碍判断会穿墙;没有访问标记则可能在两个相邻格子之间反复进入,甚至让搜索无法结束。
用 BFS 验证建模
下面用“统计岛屿数量”验证这种转换。字符 1 表示陆地,0 表示水;每发现一个尚未访问的陆地,就说明找到了一个新的连通分量,再从这里执行一次 BFS 标记整座岛屿。
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)}')预期输出
islands = 3这里没有任何显式的 graph 或邻接表,但 BFS 的本质没有变化:队列中的坐标就是待访问顶点,directions 与合法性检查共同充当邻接边生成器。
复杂度和建模边界
对于 R × C 的网格,只要每个格子至多被访问一次,时间复杂度就是 O(R × C)。访问数组占用 O(R × C) 空间,BFS 队列在极端情况下也可能保存同数量级的格子。
如果题目中的“能否走到另一个格子”只依赖当前位置,那么 (row, col) 足以表示顶点;如果移动还取决于钥匙、开关、剩余次数或其他历史信息,单独使用坐标就不再完整。此时仍然是在图上搜索,只是顶点必须从“位置”扩展为包含额外信息的状态。