bfs

BFS (kenglik bo‘yicha qidiruv) — boshlang‘ich uchdan qatlam-qatlam yuradi: avval masofasi 1 bo‘lganlar, keyin 2… Shuning uchun qirralar vazni bir xil bo‘lsa, eng qisqa yo‘lni beradi. O(V + E).

from collections import deque

dist = [-1] * n
dist[s] = 0
q = deque([s])
while q:
    v = q.popleft()
    for to in g[v]:
        if dist[to] == -1:
            dist[to] = dist[v] + 1
            q.append(to)

To‘rda (labirint)

for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
    nr, nc = r + dr, c + dc
    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#" and dist[nr][nc] == -1:
        ...

Diqqat

• Uchni navbatga qo‘shganda belgilang, olganda emas — aks holda bir uch ko‘p marta kiradi.
• Bir nechta boshlang‘ich nuqta bo‘lsa (masalan, bir nechta olov manbai), hammasini birdan navbatga qo‘ying.