Problem link ও উৎস
- **Original source:** Classic multi-source BFS distance exercise
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Medium
- **Pattern:** multi-source BFS on a grid (distance to the nearest target)
- **Basic idea inherited from:** Rotting Oranges (এই tracker-এর #8, [008-rotting-oranges.md](008-rotting-oranges.md)); multi-source BFS ([../bfs.md](../bfs.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা `m x n` binary matrix `mat` দেওয়া আছে — প্রতিটা cell হয় `0` নয় `1`। প্রতিটা cell-এর জন্য বের করো তার সবচেয়ে কাছের `0`-এর দূরত্ব কত, যেখানে দূরত্ব মাপা হয় চার দিকের (উপর-নিচ-বাম-ডান) পদক্ষেপে। উত্তর হিসেবে একই আকারের একটা matrix ফেরত দাও, যেখানে প্রতিটা ঘরে সেই দূরত্ব লেখা। (`0`-cell গুলোর দূরত্ব অবশ্যই 0।)
```text
mat: উত্তর (প্রতিটা cell -> nearest 0-এর দূরত্ব):
0 0 0 0 0 0
0 1 0 0 1 0
1 1 1 1 2 1
```
### Input ও output {#8-example-input-and-output}
```text
Input : mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
Input : mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
Edge case (একটাই 0, বাকি সব 1): mat = [[1,1],[1,0]] -> [[2,1],[1,0]]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা মাঠে কয়েকটা পানির কল (`0`) ছড়িয়ে আছে, বাকি জায়গা শুকনো (`1`)। প্রতিটা শুকনো জায়গা থেকে সবচেয়ে কাছের কলে যেতে কত পা লাগে জানতে চাও। প্রতিটা শুকনো জায়গায় দাঁড়িয়ে কল খুঁজতে বেরোনোর বদলে উল্টোটা করো: সব কল থেকে একসাথে পানি ছড়াতে দাও। যে জায়গায় পানি যত মিনিটে পৌঁছাল, সেটাই সেই জায়গার nearest কলের দূরত্ব — কারণ সবচেয়ে কাছের কলের ঢেউই আগে পৌঁছায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **multi-source BFS** (#8 Rotting Oranges)। ওখানে সব পচা কমলা একসাথে seed করে ঢেউ ছড়িয়েছিলাম; এখানে সব `0`-cell একসাথে seed করব (দূরত্ব 0), আর ঢেউ ছড়িয়ে প্রতিটা `1`-cell-কে দেবে তার nearest `0` পর্যন্ত দূরত্ব। হুবহু একই trick — শুধু "source" এবার পচা কমলা নয়, প্রতিটা `0`। BFS-এর first-arrival = shortest থিওরেমই নিশ্চিত করে প্রথম যে ঢেউ কোনো cell-কে ছোঁয়, সেটাই nearest।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **"প্রতিটা cell-এর nearest source পর্যন্ত দূরত্ব" = সব source একসাথে seed করা multi-source BFS।** ভুল পথ হবে প্রতিটা `1`-cell থেকে আলাদা করে nearest `0` খোঁজা — তাতে বহুবার BFS, খরচ বিশাল। সঠিক উল্টো চিন্তা: `0`-গুলো থেকে BFS শুরু করো; সব `0` queue-তে distance 0-তে; BFS layer ছড়ালে প্রতিটা `1`-cell প্রথমবার যে layer-এ ছোঁয়া হয়, সেটাই তার nearest `0`-এর দূরত্ব (first-arrival = shortest, কারণ সব edge cost সমান)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
- **Grid নিজেই** — implicit graph; neighbor চার দিকের cell।
- **`collections.deque`** — BFS frontier; multi-source বলে শুরুতেই সব `0`-cell ঢোকে।
- **distance matrix (`dist`)** — উত্তর; একই সাথে visited-marker (যে cell-এর dist এখনো set হয়নি, সে unvisited)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Grid-কে graph ধরা fit করে কারণ neighbor চার দিকেই fixed আর দূরত্ব মাপা step গোনা। `deque` fit করে কারণ BFS-এর FIFO-ই first-arrival = shortest নিশ্চিত করে; heap লাগে না, কারণ সব edge-এর cost সমান (1)। `dist` matrix double-duty করে — উত্তর জমা রাখে আর `dist[nr][nc] == -1` (বা সেট-হয়নি) দিয়ে visited চেক করে, আলাদা visited set বাঁচায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা `1`-cell-এর জন্য আলাদা করে nearest `0` খোঁজা — যেমন প্রতিটা `1`-cell থেকে একটা পুরো BFS চালিয়ে প্রথম `0`-তে পৌঁছানো পর্যন্ত দূরত্ব মাপা, বা প্রতিটা `1`-cell থেকে প্রতিটা `0`-cell-এর Manhattan distance তুলনা করে minimum নেওয়া।
```text
1) প্রতিটা cell (r,c) যেটা 1:
2) (r,c) থেকে BFS চালিয়ে nearest 0-এর দূরত্ব মাপো
3) সেই দূরত্ব dist[r][c]-এ লেখো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা `1`-cell থেকে আলাদা BFS মানে O(m·n) cell-এর প্রত্যেকটার জন্য O(m·n) কাজ — মোট O((m·n)^2), বড় matrix-এ অসহনীয়। সব `0`-cell-এর সাথে দূরত্ব তুলনা করলেও একই রকম খারাপ। অথচ একটাই multi-source BFS — সব `0` একসাথে seed করে — প্রতিটা cell ঠিক একবার ছোঁয়, মোট O(m·n)। মূল ভুল: দিক উল্টো; `1` থেকে `0` না খুঁজে `0` থেকে ঢেউ ছড়াও।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **BFS-টা উল্টো দিকে চালাও — `0`-গুলো থেকে, `1`-গুলো থেকে নয়।** সব `0` একসাথে distance 0-তে seed করলে এক BFS-ই প্রতিটা `1`-cell-কে তার nearest `0`-এর দূরত্ব দিয়ে দেয়, কারণ সবচেয়ে কাছের source-এর ঢেউ আগে পৌঁছায় (first-arrival = shortest)।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`dist` matrix বানাও — সব `0`-cell-এ 0, বাকি সব -1 (অসেট/unvisited)। সব `0`-cell queue-তে ঢোকাও। তারপর সাধারণ BFS: front pop করো, প্রতিটা প্রতিবেশী যার `dist == -1`, তাকে `dist[cur] + 1` দাও আর enqueue করো। queue খালি হলে `dist`-ই উত্তর। প্রতিটা cell একবার set হয় (first arrival), একবার pop হয় — O(m·n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা 1 থেকে nearest 0 খুঁজব" না ভেবে দিকটা উল্টে দাও — "সব 0 থেকে একসাথে ঢেউ ছড়াই, প্রতিটা 1 প্রথম যে ঢেউ ছোঁয় সেটাই তার উত্তর।" বহু BFS থেকে নেমে এসো একটাই reverse multi-source BFS-এ। কোন দিক থেকে শুরু করছ — সেটাই এই problem-এর আসল মোচড়।
### ছবিতে বোঝা {#7-visual-explanation}
`mat = [[0,0,0],[0,1,0],[1,1,1]]` দিয়ে ঢেউ ছড়ানো (`.` = এখনো অসেট):
```text
seed (সব 0, distance 0): ঢেউ layer 1: ঢেউ layer 2:
0 0 0 0 0 0 0 0 0
0 . 0 0 1 0 0 1 0
. . . 1 . 1 1 2 1
(1,1) layer 1-এ ছোঁয়া (উপরের/পাশের 0 থেকে)।
(2,1) layer 2-এ ছোঁয়া (তার আগে layer 1-এর 1-cell গুলো থেকে)।
উত্তর = শেষ grid
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`mat = [[1,1],[1,0]]`:
1. `dist = [[-1,-1],[-1,0]]`। queue = `[(1,1)]` (একমাত্র 0)।
2. pop `(1,1)` → প্রতিবেশী `(0,1)` (dist -1) → `dist[0][1] = 1`, enqueue; `(1,0)` (dist -1) → `dist[1][0] = 1`, enqueue।
3. pop `(0,1)` → প্রতিবেশী `(0,0)` (dist -1) → `dist[0][0] = 2`, enqueue; `(1,1)` already 0।
4. pop `(1,0)` → প্রতিবেশী `(0,0)` already 2 (set), `(1,1)` already 0। নতুন কিছু না।
5. pop `(0,0)` → প্রতিবেশী সব set। queue খালি।
6. return `dist = [[2,1],[1,0]]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
def update_matrix(mat):
R, C = len(mat), len(mat[0])
dist = [[-1] * C for _ in range(R)] # -1 মানে এখনো অসেট (unvisited)
q = deque()
# multi-source seeding: সব 0-cell distance 0-তে
for r in range(R):
for c in range(C):
if mat[r][c] == 0:
dist[r][c] = 0
q.append((r, c))
while q:
r, c = q.popleft()
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 dist[nr][nc] == -1):
dist[nr][nc] = dist[r][c] + 1 # first arrival = nearest 0
q.append((nr, nc)) # mark করার সময়ই enqueue
return dist
# ---- tests ----
m1 = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
m2 = [[0, 0, 0], [0, 1, 0], [1, 1, 1]]
m3 = [[1, 1], [1, 0]]
m4 = [[0, 1, 1, 0]]
assert update_matrix(m1) == [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
assert update_matrix(m2) == [[0, 0, 0], [0, 1, 0], [1, 2, 1]]
assert update_matrix(m3) == [[2, 1], [1, 0]]
assert update_matrix(m4) == [[0, 1, 1, 0]]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `dist = [[-1] * C ...]` — `-1` দ্বৈত কাজ করে: উত্তরের placeholder আর "এখনো visit হয়নি" চিহ্ন।
- প্রথম double loop — সব `0`-cell-কে `dist = 0` দিয়ে queue-তে (multi-source seeding)।
- `q.popleft()` — `deque`-এর O(1) front pop; FIFO-ই first-arrival = shortest নিশ্চিত করে।
- `if 0 <= nr < R and 0 <= nc < C and dist[nr][nc] == -1` — bounds আগে, তারপর শুধু অসেট প্রতিবেশী।
- `dist[nr][nc] = dist[r][c] + 1` — current cell-এর দূরত্ব + 1; প্রথম যে ঢেউ ছোঁয় সেটাই nearest।
- enqueue ঠিক set করার পাশে — mark-on-push, যাতে একই cell queue-তে বারবার না ঢোকে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`update_matrix(m2)`: সব `0` seed হয়; ঢেউ ছড়িয়ে `(1,1)` পায় 1, `(2,0)` ও `(2,2)` পায় 1, আর `(2,1)` পায় 2 → `[[0,0,0],[0,1,0],[1,2,1]]`। `m3`-এ একমাত্র 0 থেকে ছড়িয়ে `[[2,1],[1,0]]`। `m1` সব 0/একা-1 → অপরিবর্তিত। সব assert pass, শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(m · n)** — initial scan সব cell একবার; BFS-এ প্রতিটা cell ঠিক একবার set ও একবার pop হয়, প্রতিটা প্রতিবেশী constant-বার দেখা হয়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(m · n)** — `dist` matrix O(m·n), আর queue worst case একটা পুরো level (গ্রিড-আকারের) ধরে রাখতে পারে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- দিক উল্টো ধরা — `1` থেকে `0` খোঁজা; এতে multi-source-এর সুবিধাই হারায়, খরচ ফুলে যায়। সবসময় `0` থেকে ছড়াও।
- `0`-cell গুলোকে আলাদা আলাদা seed না করে একটাই super-source ভেবে গোলমাল করা — সবগুলোকে distance 0-তে queue-তে ঢোকাও।
- visited চেক বাদ দিয়ে already-set cell আবার আপডেট করা — `dist == -1` শর্তই প্রথম (nearest) মান রক্ষা করে।
- `list.pop(0)` ব্যবহার করা — প্রতি pop O(n), BFS quadratic; `deque` নাও।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: multi-source BFS (#8 Rotting Oranges) আর BFS distance theorem ([../bfs.md](../bfs.md))। Rotting Oranges-এ উত্তর ছিল level *সংখ্যা*; এখানে উত্তর প্রতিটা cell-এর *দূরত্ব* — তাই সময় না গুনে cell-এ distance store করি। মূল নতুন শিক্ষা: কখনো BFS-এর **দিক উল্টো** চালাতে হয় (target থেকে, source থেকে নয়) — এটাই multi-source-এর সবচেয়ে শক্তিশালী চিন্তা।
### পরের অনুশীলন {#22-similar-harder-problems}
- Rotting Oranges (multi-source, level = সময়) —