🗺️
AI Sketch（スケッチ） • 中級⏱️ 19 分で読める
行列とグリッド問題
グリッドとしての 2D 配列
マトリックスは単なる 2D 配列ですが、インタビューでは、地図、ボード、迷路などの グリッド を表すことがよくあります。各セル grid[r][c] はノードであり、その隣のセルは隣接セルです。
grid = [
[1, 1, 0],
[1, 0, 0],
[0, 0, 1]
]
行r、列c、寸法m × n。シンプルですが、その上に構築されたパターンは強力です。
方向性配列
4 つの個別の 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
レッスン 10 / 100%完了
ディスカッション
ログイン ディスカッションに参加