🗺️
AI 草图 • 中级⏱️ 19 分钟阅读
矩阵与网格问题
二维数组作为网格
矩阵只是一个二维数组，但在面试中它通常代表一个网格 - 地图、棋盘或迷宫。每个单元格grid[r][c]是一个节点，它的邻居是相邻单元格。
grid = [
[1, 1, 0],
[1, 0, 0],
[0, 0, 1]
]
行r，列c，尺寸m × n。简单 - 但构建在其之上的模式非常强大。
定向数组
不要编写四个单独的 if 语句，而是使用 方向数组：
# 4-directional (up, down, left, right)
dirs = [(-1,0), (1,0), (0,-1), (0,1)]
# 8-directional (includes diagonals)
dirs = [(-1,0),(1,0),(0,-1),(0,1),
(-1,-1),(-1,1),(1,-1),(1,1)]
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
# process neighbour
这是网格问题中最可重用的片段。
🤯
方向数组技巧有时称为“增量编码”。它出现在游戏开发、图像处理和竞技编程中——任何使用网格的地方。
网格上的 BFS - 迷宫中的最短路径
BFS 在未加权网格中找到最短路径。从源开始，探索距离 1 处的所有邻居，然后探索距离 2 处的所有邻居，依此类推。
from collections import deque
def shortest_path(grid, start, end):
m, n = len(grid), len(grid[0])
q = deque([(start[0], start[1], 0)])
visited = {(start[0], start[1])}
dirs = [(-1,0),(1,0),(0,-1),(0,1)]
while q:
r, c, dist = q.popleft()
if (r, c) == end:
return dist
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<m and 0<=nc<n and (nr,nc) not in visited and grid[nr][nc]==0:
visited.add((nr, nc))
q.append((nr, nc, dist+1))
return -1
网格上的 DFS - 洪水填充和岛屿数量
洪水填充（如油漆桶工具）：从起始单元格开始，更改所有连接的相同颜色的单元格。 DFS 或 BFS 都可以。
岛屿数量： 扫描网格；当您找到 1 时，运行 DFS/BFS 将整个岛屿标记为已访问，然后增加计数。
def num_islands(grid):
count = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == '1':
dfs(grid, r, c) # mark island
count += 1
return count
🧠小测验
在”岛屿数量”中，为什么我们将单元格标记为 DFS 期间访问过的单元格？
第 10 课，共 10 课已完成 0%
讨论
登录 参与讨论