Problem link ও উৎস
- **Original source:** Classic multi-source BFS exercise
- **Platform:** LeetCode —
- **Topic:** queue (multi-source BFS)
- **Difficulty:** Medium
- **Pattern:** multi-source BFS — queue
- **Basic idea inherited from:** Problem 12 (BFS frontier), কিন্তু একসাথে কয়েকটা start নিয়ে; পূর্ণ তত্ত্ব [../../09-graphs/](../../09-graphs/README.md)-এ
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা grid দেওয়া আছে যেখানে প্রতিটা ঘর তিন রকম: `0` = খালি, `1` = তাজা কমলা, `2` = পচা কমলা। প্রতি মিনিটে একটা পচা কমলা তার পাশের (উপর-নিচ-ডান-বাঁ) তাজা কমলাগুলোকে পচিয়ে দেয়। সব তাজা কমলা পচতে **কত মিনিট** লাগবে বলো; যদি কোনো তাজা কমলা কখনোই পচানো না যায় (যেমন আলাদা হয়ে আছে), তবে `-1`।
```text
2 1 1 minute 0: শুধু (0,0) পচা
1 1 0 ...ছড়াতে ছড়াতে...
0 1 1 minute 4: সব পচে গেছে -> উত্তর 4
```
### Input ও output {#8-example-input-and-output}
```text
Input : [[2,1,1],[1,1,0],[0,1,1]] -> Output: 4
Input : [[2,1,1],[0,1,1],[1,0,1]] -> Output: -1 ((2,0)-র তাজা কমলা আলাদা)
Input : [[0,2]] -> Output: 0 (তাজা কমলাই নেই)
Edge case 1 (একটাও পচা নেই) : [[1]] -> -1 (পচানোর কেউ নেই)
Edge case 2 (শুধু খালি+পচা) : [[2,0]] -> 0 (পচানোর তাজা নেই)
Edge case 3 (সবই তাজা, ছোঁয়া যায় না): [[1,1]] -> -1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা পুকুরের নানা জায়গায় একসাথে কয়েকটা পাথর ছুঁড়লে ভাবো। প্রতিটা পাথর থেকে ঢেউ বাইরের দিকে ছড়ায়; ঢেউগুলো একই গতিতে এগোয় আর যেখানে মেলে সেখানে মিশে যায়। পানির কোনো বিন্দু প্রথম যে ঢেউয়ে ভেজে, সেটাই তার সবচেয়ে কাছের পাথর থেকে আসা। সব পচা কমলা = একসাথে ছোঁড়া পাথর; পচন = একসাথে ছড়ানো ঢেউ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **Problem 12 (Number of Islands)**-এর BFS-এর সরাসরি সম্প্রসারণ, একটা মোচড় নিয়ে: এক জায়গা থেকে নয়, **একসাথে অনেক জায়গা থেকে** ছড়ানো শুরু — এটাই **multi-source BFS**। শুরুর সব পচা কমলা একসাথে queue-তে থাকে যেন তারা সবাই minute 0-তে দাঁড়িয়ে আছে, তারপর সবাই একসাথে একধাপ করে ছড়ায়। পূর্ণ graph-তত্ত্ব [../../09-graphs/](../../09-graphs/README.md)-এ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **simultaneous wavefront**: সব পচা কমলাকে যদি একই BFS-এর level 0 ধরো, তাহলে BFS-এর প্রতিটা পরবর্তী level ঠিক "এক মিনিট পরের অবস্থা"। কোনো তাজা কমলায় BFS প্রথমবার পৌঁছানো মানেই — যেহেতু FIFO কোনো level-কে আগের level-এর আগে শেষ করতে দেয় না — সেটা সবচেয়ে কাছের পচা উৎস থেকে minimum সময়ে পচল।
শেষে যদি কোনো তাজা কমলা থেকে যায় (কোনো উৎসই তাকে ছুঁতে পারেনি), উত্তর `-1`।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **queue** (`collections.deque`) যাতে *শুরুতেই সব পচা কমলার* `(row, col)` ঢোকানো থাকে। সাথে একটা `fresh` counter (কয়টা তাজা কমলা বাকি) — শেষে এটা `0` কিনা দেখে আমরা বুঝি সব পচেছে নাকি `-1` দিতে হবে। আর একটা `minutes` counter, level-by-level গোনার জন্য।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
"প্রতি মিনিটে এক ধাপ ছড়ায়" — এটাই BFS-এর level structure। queue-র FIFO order নিশ্চিত করে minute-d-এর সব কমলা minute-(d+1)-এর কারো আগে process হয়। `len(queue)`-এর snapshot নিয়ে একটা পুরো level একবারে process করলে আমরা ঠিক ঠিক মিনিট গুনতে পারি। একাধিক উৎস queue-তে একসাথে থাকায় কোনো বাড়তি কাঠামো ছাড়াই "সব একসাথে ছড়াচ্ছে" ব্যাপারটা পাওয়া যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: প্রতি মিনিটে পুরো grid scan করো; এই মিনিটে যেসব ঘর `2`, তাদের তাজা প্রতিবেশীদের চিহ্নিত করে পরের scan-এ `2` বানাও; যতক্ষণ কোনো নতুন পচন ঘটে ততক্ষণ minute বাড়াও।
```text
each minute: পুরো grid scan -> পচা কমলার পাশের তাজাদের পচাও -> minute++
কোনো নতুন পচন না হলে থামো; তখন তাজা থাকলে -1, নাহলে minute
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতি মিনিটে পুরো grid নতুন করে scan করা মানে কাজটা `(মিনিট সংখ্যা) × (grid আকার)` — সবচেয়ে খারাপ ক্ষেত্রে এক প্রান্ত থেকে অন্য প্রান্তে পচন ছড়াতে অনেক মিনিট, প্রতিবার গোটা grid scan। multi-source BFS প্রতিটা ঘর ঠিক একবার ছোঁয়, তাই **O(rows × cols)**।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: সব পচা কমলাকে BFS-এর একই starting level-এ রাখলে, BFS-এর গভীরতা (level সংখ্যা) হুবহু মিনিট-সংখ্যা হয়ে যায়। তাই "কতগুলো মিনিট" প্রশ্নটা পরিণত হয় "multi-source BFS-এর সর্বোচ্চ distance"-এ — একবার scan-এ পাওয়া যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রথমে পুরো grid scan করে সব পচা কমলা queue-তে ঢোকাও আর তাজা কমলা গোনো। তারপর level-by-level BFS: প্রতি iteration-এ `minutes` এক বাড়াও, এবং `len(queue)` snapshot ধরে ওই level-এর সব কমলা popleft করে তাদের তাজা প্রতিবেশীদের পচাও (grid-এ `2` লেখো, `fresh` কমাও, queue-তে দাও)। loop চলে যতক্ষণ queue খালি না হয় আর তাজা বাকি থাকে। শেষে `fresh == 0` হলে `minutes`, নাহলে `-1`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "একটা একটা করে উৎস থেকে BFS চালাই" না ভেবে ভাবো "সব উৎসকে একই super-source-এর সন্তান ধরি, সবাই minute 0-তে দাঁড়ানো"। এক BFS-এই সব wavefront সমান্তরালে চলে, আর কোনো ঘর প্রথমবার ভিজলেই সেটা minimum সময়, কারণ কোনো ঢেউ আগের ঢেউকে টপকায় না।
### ছবিতে বোঝা {#7-visual-explanation}
`[[2,1,1],[1,1,0],[0,1,1]]`-এ wavefront (minute হিসাব করি):
```text
start: queue=[(0,0)] (একমাত্র পচা), fresh=6, minutes=0
min1: pop (0,0) -> (1,0),(0,1) পচাও queue=[(1,0),(0,1)] fresh=4
min2: pop (1,0),(0,1) -> (1,1),(0,2) পচাও queue=[(1,1),(0,2)] fresh=2
min3: pop (1,1),(0,2) -> (2,1) পচাও queue=[(2,1)] fresh=1
min4: pop (2,1) -> (2,2) পচাও queue=[(2,2)] fresh=0
fresh==0 -> থামো -> উত্তর = 4
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[[2,1],[1,1]]`:
1. scan: পচা `(0,0)` → queue; তাজা `(0,1),(1,0),(1,1)` → `fresh = 3`; `minutes = 0`
2. queue non-empty আর `fresh>0` → `minutes = 1`; এই level-এ `(0,0)` pop → `(0,1)` পচাও (`fresh=2`), `(1,0)` পচাও (`fresh=1`); queue = `[(0,1),(1,0)]`
3. `minutes = 2`; level: `(0,1)` pop → `(1,1)` পচাও (`fresh=0`); `(1,0)` pop → প্রতিবেশী সব পচা/সীমার বাইরে
4. `fresh == 0` → loop থামে → return `minutes = 2`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
def oranges_rotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows): # সব পচা একসাথে source
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while queue and fresh > 0: # level-by-level
minutes += 1
for _ in range(len(queue)): # এই মিনিটের snapshot
r, c = queue.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2 # পচিয়ে দাও
fresh -= 1
queue.append((nr, nc))
return minutes if fresh == 0 else -1 # বাকি তাজা থাকলে -1
# ---- tests ----
assert oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]) == 4
assert oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]) == -1 # আলাদা তাজা
assert oranges_rotting([[0, 2]]) == 0 # তাজা নেই
assert oranges_rotting([[1]]) == -1 # পচা নেই
assert oranges_rotting([[2, 0]]) == 0 # তাজা নেই
assert oranges_rotting([[1, 1]]) == -1 # ছোঁয়া যায় না
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- প্রথম double loop — সব পচা কমলা queue-তে (multi-source), আর তাজা কমলা গুনে `fresh`-এ।
- `while queue and fresh > 0:` — frontier থাকলে আর এখনো তাজা বাকি থাকলেই চালাও; `fresh==0` হলে অযথা ঘোরে না।
- `minutes += 1` — প্রতিটা BFS level মানে এক মিনিট।
- `for _ in range(len(queue)):` — snapshot; এই মিনিটে যারা queue-তে ছিল শুধু তাদেরই process করো, এই মিনিটে যোগ-হওয়াদের নয়।
- ভেতরের `if`— তাজা প্রতিবেশী পেলে তাকে `2` করো, `fresh` কমাও, queue-তে দাও।
- `return minutes if fresh == 0 else -1` — সব পচলে মিনিট; কেউ বাকি থাকলে `-1`। (শুরুতেই `fresh==0` হলে loop চলে না, `minutes` থাকে `0`।)
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`oranges_rotting([[2,1,1],[1,1,0],[0,1,1]])` → section 7-এর wavefront মতো 4 মিনিটে সব পচে, `fresh` শেষে `0` → `4`। `oranges_rotting([[2,1,1],[0,1,1],[1,0,1]])` → `(2,0)`-র তাজা কমলা চারপাশে খালি দিয়ে ঘেরা, কখনো পচে না, শেষে `fresh>0` → `-1`। সব assert pass করে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(rows × cols)** — শুরুর scan পুরো grid একবার, আর BFS-এ প্রতিটা ঘর বড়জোর একবার enqueue/dequeue হয়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(rows × cols)** — queue সবচেয়ে খারাপ ক্ষেত্রে (শুরুতেই প্রায় সব পচা, বা একসাথে অনেক ঘর frontier-এ) এতটা বড় হতে পারে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `len(queue)` snapshot না নিয়ে level mix করা — তখন এক মিনিটে যোগ-হওয়া কমলাও একই মিনিটে process হয়ে মিনিট গণনা ভুল হয়।
- শুরুতে তাজা কমলা না গোনা — `-1` কেস (কেউ পচে না) ধরা যায় না।
- `fresh==0`-এর প্রাথমিক কেস ভুলে যাওয়া — তাজা কমলা না থাকলে উত্তর `0`, `-1` নয়; loop না চললে `minutes` `0`-ই থাকে বলে এটা এমনিতেই ঠিক হয়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Problem 12-এর single-source BFS, এখানে multi-source-এ সম্প্রসারিত। chapter-এর [../patterns.md](../patterns.md)-এর Pattern 2 (BFS Frontier) এখানে layered/multi-source রূপে; পূর্ণ আলোচনা [../../09-graphs/](../../09-graphs/README.md)-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- 01 Matrix (নিকটতম 0 পর্যন্ত দূরত্ব, multi-source BFS) —