🗺️
AI Sketch • Gemiddeld⏱️ 19 min leestijd
Matrix- en rasterproblemen
2D-Arrays als Grids
Een matrix is gewoon een 2D-array, maar in interviews stelt het vaak een grid voor - een kaart, een bord of een doolhof. Elke cel grid[r][c] is een knooppunt, en de buren zijn aangrenzende cellen.
grid = [
[1, 1, 0],
[1, 0, 0],
[0, 0, 1]
]
Rij r, kolom c, afmetingen m × n. Eenvoudig - maar de patronen die erop gebouwd worden zijn krachtig.
Richtingsarrays
In plaats van vier aparte if-statements, gebruik een richtingsarray:
# 4 richtingen (boven, onder, links, rechts)
dirs = [(-1,0), (1,0), (0,-1), (0,1)]
# 8 richtingen (inclusief diagonalen)
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:
# verwerk buur
Dit is het meest herbruikbare stukje code in gridproblemen.
🤯
De richtingsarray-truc wordt soms "delta-encoding" genoemd. Het komt voor in game-ontwikkeling, beeldverwerking en competitive programming - overal waar grids worden gebruikt.
BFS op een Grid - Kortste Pad in een Doolhof
BFS vindt het kortste pad in een ongewogen grid. Begin bij de bron, verken alle buren op afstand 1, dan afstand 2, enzovoort.
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 op een Grid - Flood Fill en Eilanden Tellen
Flood fill (zoals het verfemmertje): vanaf een startcel verander je alle verbonden cellen met dezelfde kleur. DFS of BFS werken beide.
Les 10 van 100% voltooid
Discussie
Inloggen deelnemen aan de discussie