🗺️
AI Sketch • Intermédiaire⏱️ 19 min de lecture
Problèmes de matrices et grilles
Tableaux 2D comme grilles
Une matrice est simplement un tableau 2D, mais en entretien elle représente souvent une grille - une carte, un plateau ou un labyrinthe. Chaque cellule grid[r][c] est un nœud, et ses voisins sont les cellules adjacentes.
grid = [
[1, 1, 0],
[1, 0, 0],
[0, 0, 1]
]
Ligne r, colonne c, dimensions m × n. Simple - mais les patrons construits dessus sont puissants.
Tableaux de directions
Au lieu d'écrire quatre instructions if séparées, utilisez un tableau de directions :
# 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
C'est l'extrait de code le plus réutilisable dans les problèmes de grilles.
🤯
L'astuce du tableau de directions est parfois appelée « delta encoding ». On la retrouve en développement de jeux, traitement d'images et programmation compétitive - partout où il y a des grilles.
BFS sur une grille - Plus court chemin dans un labyrinthe
Le BFS trouve le plus court chemin dans une grille non pondérée. On part de la source, on explore tous les voisins à distance 1, puis à distance 2, et ainsi de suite.
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 sur une grille - Flood Fill et Nombre d'îles
Leçon 10 sur 100% terminé
Discussion
Sign in to join the discussion