جستوجوی سطحی برای کوتاهترین مسیر بدون وزن
آمادگی مصاحبهٔ الگوریتمی با Python
- In 75 minutes, introduce first-in-first-out processing with collections.deque and constant-time popleft.
- Recognize minimum edge counts and simultaneous spread as BFS signals; explain why unequal edge costs invalidate ordinary BFS shortest-path guarantees.
- Independently select initial queue contents for computing each binary-grid cell's distance to its nearest zero.
- Develop 01 Matrix from separate searches for each cell to a multi-source Python BFS starting from all zero cells.
- Mark cells when enqueued and prove that queue layers assign shortest distances in nondecreasing order.
- Derive O(rows * columns) time and space while distinguishing distance output storage from the queue.
- Test one-cell grids, all-zero grids, one distant zero, and the agreed no-zero contract; diagnose list pop(0), repeated enqueues, and incorrect distance increments.
BFS: کمترین حرکت، نه کمترین هزینه
```svg
<svg viewBox="0 0 800 500" xmlns="http://www.w3.org/2000/svg"><path class="tm-line" d="M130 75 H650 M130 75 L300 155 H480 L650 75" stroke-width="3" fill="none"/><circle class="tm-accent" cx="130" cy="75" r="29"/><circle class="tm-soft" cx="300" cy="155" r="24"/><circle class="tm-soft" cx="480" cy="155" r="24"/><circle class="tm-green" cx="650" cy="75" r="29"/><text class="tm-text" x="130" y="32" text-anchor="middle" font-size="20" direction="rtl">شروع</text><text class="tm-text" x="650" y="32" text-anchor="middle" font-size="20" direction="rtl">مقصد</text><text class="tm-text2" x="390" y="58" text-anchor="middle" font-size="18" direction="rtl">مسیر مستقیم</text><path class="tm-line-accent" d="M130 75 L300 155 H480 L650 75" stroke-width="5" fill="none"/><text class="tm-text-accent" x="390" y="205" text-anchor="middle" font-size="19" direction="rtl">DFS: کشف پس از سه حرکت</text><text class="tm-text-green" x="390" y="91" text-anchor="middle" font-size="18" direction="rtl">فقط یک حرکت</text><rect class="tm-soft" x="90" y="230" width="620" height="110" rx="14"/><text class="tm-text" x="400" y="256" text-anchor="middle" font-size="19" direction="rtl">BFS: صف با ترتیب FIFO</text><rect class="tm-accent" x="280" y="270" width="100" height="36" rx="8"/><rect class="tm-surface" x="420" y="270" width="100" height="36" rx="8"/><text class="tm-text" x="330" y="295" text-anchor="middle" font-size="17" direction="rtl">نقطهٔ اول</text><text class="tm-text" x="470" y="295" text-anchor="middle" font-size="17" direction="rtl">نقطهٔ دوم</text><path class="tm-line-accent" d="M270 288 H195 M205 280 L195 288 L205 296 M610 288 H530 M540 280 L530 288 L540 296" fill="none" stroke-width="2"/><text class="tm-text2" x="170" y="325" text-anchor="middle" font-size="16">popleft</text><text class="tm-text2" x="610" y="325" text-anchor="middle" font-size="16">append</text><rect class="tm-gold tm-enter" x="90" y="355" width="620" height="125" rx="14"/><text class="tm-text" x="400" y="382" text-anchor="middle" font-size="20" direction="rtl">وزنهای نابرابر: تضمین نداریم</text><text class="tm-text" x="400" y="415" text-anchor="middle" font-size="18" direction="rtl">مسیر مستقیم: یک حرکت، هزینهٔ ده</text><text class="tm-text" x="400" y="444" text-anchor="middle" font-size="18" direction="rtl">مسیر دوحرکتی: هر حرکت یک، هزینهٔ کل دو</text><text class="tm-text-accent" x="400" y="470" text-anchor="middle" font-size="17" direction="rtl">حرکت کمتر، لزوماً هزینهٔ کمتر نیست</text></svg>
```
شروع مشترک از همهٔ صفرها
```svg
<svg viewBox="0 0 800 470" xmlns="http://www.w3.org/2000/svg"><text x="190" y="35" text-anchor="middle" class="tm-text" font-size="21" direction="rtl">ورودی 01 Matrix</text><text x="190" y="67" text-anchor="middle" class="tm-muted" font-size="16" direction="rtl">حرکت: بالا، پایین، چپ، راست</text><rect x="70" y="100" width="75" height="70" rx="8" class="tm-green"/><rect x="150" y="100" width="75" height="70" rx="8" class="tm-surface"/><rect x="230" y="100" width="75" height="70" rx="8" class="tm-surface"/><rect x="70" y="175" width="75" height="70" rx="8" class="tm-surface"/><rect x="150" y="175" width="75" height="70" rx="8" class="tm-surface"/><rect x="230" y="175" width="75" height="70" rx="8" class="tm-green"/><g font-size="26" text-anchor="middle"><text x="107" y="144" class="tm-text">0</text><text x="187" y="144" class="tm-text">1</text><text x="267" y="144" class="tm-text">1</text><text x="107" y="219" class="tm-text">1</text><text x="187" y="219" class="tm-text">1</text><text x="267" y="219" class="tm-text">0</text></g><text x="555" y="35" text-anchor="middle" class="tm-text" font-size="21" direction="rtl">فاصلهها در multi-source BFS</text><text x="475" y="86" text-anchor="middle" class="tm-muted" font-size="14">0</text><text x="555" y="86" text-anchor="middle" class="tm-muted" font-size="14">1</text><text x="635" y="86" text-anchor="middle" class="tm-muted" font-size="14">2</text><text x="420" y="144" text-anchor="middle" class="tm-muted" font-size="14">0</text><text x="420" y="219" text-anchor="middle" class="tm-muted" font-size="14">1</text><rect x="438" y="100" width="75" height="70" rx="8" class="tm-green"/><rect x="518" y="100" width="75" height="70" rx="8" class="tm-accent"/><rect x="598" y="100" width="75" height="70" rx="8" class="tm-gold"/><rect x="438" y="175" width="75" height="70" rx="8" class="tm-accent"/><rect x="518" y="175" width="75" height="70" rx="8" class="tm-gold"/><rect x="598" y="175" width="75" height="70" rx="8" class="tm-green"/><g font-size="26" text-anchor="middle"><text x="475" y="144" class="tm-text">0</text><text x="555" y="144" class="tm-text">1</text><text x="635" y="144" class="tm-text">1</text><text x="475" y="219" class="tm-text">1</text><text x="555" y="219" class="tm-text">1</text><text x="635" y="219" class="tm-text">0</text></g><text x="555" y="280" text-anchor="middle" class="tm-text" font-size="18" direction="rtl">صف خالی؛ جواب نهایی</text><text x="400" y="320" text-anchor="middle" class="tm-text2" font-size="17" direction="rtl">خانههای فاصلهٔ 1: بدون کشف تازه</text><text x="400" y="370" text-anchor="middle" class="tm-muted" font-size="16" direction="rtl">ورودی خالی ← خروجی خالی؛ ورودی بدون تغییر</text><text x="400" y="407" text-anchor="middle" class="tm-muted" font-size="16" direction="rtl">بدون صفر: همهٔ فاصلهها −1</text></svg>
```
اولین کشف، کوتاهترین فاصله
```svg
<svg viewBox="0 0 900 680" xmlns="http://www.w3.org/2000/svg"><defs><marker id="arr" markerWidth="8" markerHeight="8" refX="7" refY="4" orient="auto"><path d="M0 0 L8 4 L0 8" class="tm-arrow"/></marker></defs><text x="450" y="30" text-anchor="middle" class="tm-text" font-size="21" direction="rtl">FIFO: ترتیب پردازش لایهها</text><rect x="170" y="50" width="120" height="48" rx="10" class="tm-green"/><rect x="360" y="50" width="120" height="48" rx="10" class="tm-soft"/><rect x="550" y="50" width="120" height="48" rx="10" class="tm-soft"/><text x="230" y="81" text-anchor="middle" class="tm-text" font-size="24">0</text><text x="420" y="81" text-anchor="middle" class="tm-text" font-size="24">1</text><text x="610" y="81" text-anchor="middle" class="tm-text" font-size="24">2 …</text><path d="M295 74 H350 M485 74 H540" class="tm-line-accent" marker-end="url(#arr)"/><text x="450" y="128" text-anchor="middle" class="tm-text2" font-size="17" direction="rtl">فاصلهٔ خروجی هیچوقت کم نمیشود</text><rect x="25" y="155" width="410" height="240" rx="14" class="tm-surface"/><text x="230" y="183" text-anchor="middle" class="tm-text" font-size="19" direction="rtl">چهار خانهٔ پشت سر هم</text><text x="230" y="215" text-anchor="middle" class="tm-text2" font-size="19" direction="rtl">مقدارها: 0 ، 1 ، 1 ، 1</text><text x="230" y="248" text-anchor="middle" class="tm-text" font-size="21">0, −1, −1, −1</text><text x="230" y="280" text-anchor="middle" class="tm-text" font-size="21">0, 1, −1, −1</text><text x="230" y="312" text-anchor="middle" class="tm-text" font-size="21">0, 1, 2, −1</text><text x="230" y="344" text-anchor="middle" class="tm-text-green" font-size="21">0, 1, 2, 3</text><text x="230" y="377" text-anchor="middle" class="tm-muted" font-size="16" direction="rtl">صف خالی</text><rect x="455" y="155" width="420" height="240" rx="14" class="tm-soft"/><text x="665" y="185" text-anchor="middle" class="tm-text" font-size="19" direction="rtl">فرضِ راه کوتاهتر</text><circle cx="510" cy="254" r="25" class="tm-green"/><circle cx="640" cy="254" r="25" class="tm-surface"/><circle cx="810" cy="254" r="30" class="tm-accent"/><text x="510" y="262" text-anchor="middle" class="tm-text" font-size="23">0</text><text x="640" y="262" text-anchor="middle" class="tm-text" font-size="23">1</text><text x="810" y="262" text-anchor="middle" class="tm-text" font-size="23">3</text><path d="M538 254 H610 M669 254 H775" class="tm-line-accent" marker-end="url(#arr)"/><text x="725" y="235" text-anchor="middle" class="tm-text2" font-size="16" direction="rtl">کشف با 2</text><text x="665" y="322" text-anchor="middle" class="tm-text-accent" font-size="18" direction="rtl">لایهٔ 1 زودتر پردازش شده: تناقض</text><text x="665" y="364" text-anchor="middle" class="tm-text2" font-size="17" direction="rtl">همهٔ صفرها در لایهٔ 0 شروع میکنند</text><text x="230" y="428" text-anchor="middle" class="tm-text" font-size="18" direction="rtl">ثبت هنگام خروج: خطر ورود دوباره</text><rect x="100" y="448" width="70" height="60" rx="8" class="tm-green"/><rect x="270" y="448" width="70" height="60" rx="8" class="tm-soft"/><rect x="100" y="558" width="70" height="60" rx="8" class="tm-soft"/><rect x="270" y="558" width="70" height="60" rx="8" class="tm-accent"/><text x="135" y="485" text-anchor="middle" class="tm-text" font-size="22">0</text><text x="305" y="485" text-anchor="middle" class="tm-text" font-size="22">1</text><text x="135" y="595" text-anchor="middle" class="tm-text" font-size="22">1</text><text x="305" y="595" text-anchor="middle" class="tm-text" font-size="22">1</text><path d="M175 478 H260 M135 513 V548 M305 513 V548 M175 588 H260" class="tm-line-accent" marker-end="url(#arr)"/><text x="230" y="650" text-anchor="middle" class="tm-text-accent" font-size="16" direction="rtl">دو مسیر به پایین راست؛ بدون بررسی، رفتوبرگشت</text><rect x="455" y="420" width="420" height="240" rx="14" class="tm-green tm-enter"/><text x="665" y="451" text-anchor="middle" class="tm-text" font-size="20" direction="rtl">کشف در لحظهٔ ورود</text><text x="665" y="493" text-anchor="middle" class="tm-text" font-size="19" direction="rtl">فقط فاصلهٔ −1 را قبول کن</text><text x="665" y="535" text-anchor="middle" class="tm-text" font-size="19" direction="rtl">فاصله را بنویس</text><path d="M665 544 V567" class="tm-line-accent" marker-end="url(#arr)"/><text x="665" y="591" text-anchor="middle" class="tm-text" font-size="19" direction="rtl">بعد وارد صف کن</text><text x="665" y="634" text-anchor="middle" class="tm-text-green" font-size="18" direction="rtl">کوتاهترین فاصله؛ فقط یک ورود</text></svg>
```
پیادهسازی کامل با deque و dist
```python
from collections import deque
def updateMatrix(mat):
if not mat or not mat[0]:
return []
rows, cols = len(mat), len(mat[0])
dist = [[-1] * cols for _ in range(rows)]
queue = deque()
# مقداردهی اولیه: همهٔ صفرها، پیش از پردازش صف
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
dist[r][c] = 0
queue.append((r, c))
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# کشف همسایهها: ثبت فاصله پیش از ورود به صف
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
if dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return dist
```
- **ردیفهای مستقل:** هر ردیفِ `dist` جدا ساخته میشود؛ نه با تکرار یک لیستِ ردیف.
- **فاصله از خانهٔ فعلی:** `dist[r][c] + 1`، نه شمارندهٔ تعداد خروجها. دو صفرِ پیاپی، هر دو همسایهٔ تازه را با فاصلهٔ \(1\) کشف میکنند.
تستهای مرزی و هزینهٔ خطی
قرارداد بدون صفر: فاصلهها برابر \(-1\) میمانند؛ هیچ خانهای وارد صف نمیشود.
**تکخانهها**
\[ [0]\longmapsto[0],\qquad [1]\longmapsto[-1] \]
**تمامصفر و ورودی خالی**
\[ \mathbf{0}_{\mathrm{rows}\times\mathrm{cols}}\longmapsto\mathbf{0}_{\mathrm{rows}\times\mathrm{cols}},\qquad []\longmapsto[] \]
تمامصفر: همه از ابتدا در صف؛ بدون ورود دوباره.
**صفرِ دور: ورودی**
\[ \mathrm{mat}=\begin{bmatrix}0&1&1\\1&1&1\end{bmatrix} \]
فاصلهٔ هر خانه تا صفر را پیشبینی کن.
**فاصلههای مورد انتظار**
\[ \mathrm{dist}=\begin{bmatrix}0&1&2\\1&2&3\end{bmatrix} \]
پایین راست: \(3\) حرکت. اختلاف؟ شرط کشف و محل افزودن \(1\) را بررسی کن.
**پیمایش اولیه**
\[ N=\mathrm{rows}\cdot\mathrm{cols},\qquad T_{\mathrm{init}}=\Theta(N) \]
ساخت dist و پیدا کردن همهٔ صفرها.
**شمارش ورودهای یکتا**
\[ \begin{aligned}\#\mathrm{enqueue}&\le N\\\#\mathrm{dequeue}&\le N\\\#\mathrm{neighbor\ checks}&\le4N\\T&=\Theta(N)=\Theta(\mathrm{rows}\cdot\mathrm{cols})\end{aligned} \]
با deque و popleft در \(O(1)\)؛ استفاده از list.pop(0) میتواند کران خطی را خراب کند.
**فضای خروجی**
\[ S_{\mathrm{dist}}=\Theta(N) \]
برای هر خانه یک فاصله نگه میداریم.
**فضای کمکی در بدترین حالت**
\[ \begin{aligned}\max|\mathrm{queue}|&=N\quad(\mathrm{mat}=\mathbf{0})\\S_{\mathrm{aux}}&=\Theta(N)=\Theta(\mathrm{rows}\cdot\mathrm{cols})\end{aligned} \]
حتی بدون شمردن خروجی، فضا خطی است. تمرین: علامتزدن هنگام ورود را حذف کن و ورودهای تکراری را روی مربع \(2\times2\) پیدا کن.
بازگشت به دوره