Problem link ও উৎস
- **Original source:** Classic multi-source BFS exercise
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Medium
- **Pattern:** multi-source BFS on a grid (answer = number of levels)
- **Basic idea inherited from:** queue দিয়ে BFS ([../../04-stack-and-queue/](../../04-stack-and-queue/README.md), [../bfs.md](../bfs.md)); level-by-level expansion
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা `m x n` grid দেওয়া আছে, যেখানে প্রতিটা cell-এর মান `0` (খালি), `1` (তাজা কমলা), বা `2` (পচা কমলা)। প্রতি মিনিটে যেকোনো পচা কমলার চার দিকের (উপর-নিচ-বাম-ডান) তাজা প্রতিবেশী কমলাগুলো পচে যায়। বলো: সব কমলা পচতে কত মিনিট লাগবে। যদি কোনো তাজা কমলা কখনোই পচতে না পারে (চারদিকে আটকা / পচা থেকে দূরে), তাহলে `-1`।
```text
grid (0=খালি, 1=তাজা, 2=পচা):
2 1 1
1 1 0
0 1 1 <- সব পচতে লাগে 4 মিনিট
```
### Input ও output {#8-example-input-and-output}
```text
Input : grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Input : grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1 (নিচ-বাঁয়ের (2,0) কমলা কখনো পচা ছোঁবে না)
Edge case (কোনো তাজা কমলাই নেই): grid = [[0,2]] -> 0 (শুরুতেই সব "পচা/খালি")
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ঝুড়িভর্তি কমলার মধ্যে কয়েকটা আগেই পচা ভাবো। পচন ছোঁয়াচে — প্রতি রাতে প্রতিটা পচা কমলা তার গা-ঘেঁষা তাজা কমলাগুলোকে পচিয়ে দেয়। সব পচা কমলা একসাথে এই কাজ করে, তাই পচন একসাথে অনেক জায়গা থেকে ছড়ায়। কত রাতে পুরো ঝুড়ি পচবে? — এটাই উত্তর। আর কোনো তাজা কমলা যদি চারপাশে খালি জায়গা/দেয়ালে আটকে পচা থেকে বিচ্ছিন্ন থাকে, সে কখনো পচবে না — তখন উত্তর `-1`।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **queue দিয়ে BFS** ([../../04-stack-and-queue/](../../04-stack-and-queue/README.md), [../bfs.md](../bfs.md)), বিশেষ করে তার **multi-source** রূপ। পচন একটা ঢেউয়ের মতো একসাথে ছড়ায় — সব পচা কমলা থেকে একসাথে। BFS-এর সৌন্দর্য: queue-টা শুধু একটা start দিয়ে নয়, **সব** পচা কমলা দিয়ে শুরু করো (সবাই minute 0-এ); তারপর সাধারণ BFS চললেই প্রতিটা তাজা কমলা পায় তার nearest পচা কমলা থেকে সময়। উত্তর = মোট কত level লাগল।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **সমান-cost ছড়ানোয় BFS-এর level সংখ্যা = সময়।** প্রতিটা মিনিট হলো BFS-এর এক layer; layer 0 = প্রথম থেকে পচা সব কমলা, layer 1 = তাদের প্রতিবেশী, layer 2 = তাদেরও প্রতিবেশী — এভাবে। সব sources একসাথে queue-তে থাকায় ঢেউগুলো মেলে, আর প্রতিটা তাজা কমলা পচে যায় তার সবচেয়ে কাছের পচা কমলার সময়ে (BFS-এর first-arrival = shortest)। শেষ যে layer-এ নতুন কমলা পচল, সেটাই মোট মিনিট। শেষে কোনো তাজা কমলা বাকি থাকলে — অপৌঁছনীয়, তাই `-1`।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
- **Grid নিজেই** — implicit graph; neighbor চার দিকের cell।
- **`collections.deque`** — BFS frontier; multi-source বলে শুরুতেই সব পচা কমলা ঢোকে।
- **fresh counter** — কতগুলো তাজা কমলা এখনো পচেনি, শেষে `-1` নাকি minute সিদ্ধান্তে।
- **distance/minute চিহ্ন** — হয় cell-এর সাথে সময় store করে (`2` করে দিয়ে), নয়তো level-by-level গুনে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Grid-কে graph ধরা fit করে কারণ neighbor সম্পর্ক চার দিকেই fixed। `deque` fit করে কারণ BFS-এর গোটা চরিত্রই FIFO — যা আগে পচল, তার প্রতিবেশী আগে পচায়; `list.pop(0)` হলে quadratic হয়ে যেত। multi-source seeding fit করে কারণ পচন আক্ষরিক অর্থেই একাধিক জায়গা থেকে একসাথে ছড়ায় — এক পাথরের বদলে এক মুঠো পাথর পুকুরে ফেলার মতো, একই ঢেউ একই code।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: minute-কে simulate করা grid বারবার scan করে — প্রতি minute-এ পুরো grid ঘুরে যেসব তাজা কমলার কোনো পচা প্রতিবেশী আছে তাদের চিহ্নিত করো, তারপর সবাইকে একসাথে পচাও; এভাবে যতক্ষণ না কোনো নতুন কমলা পচে।
```text
1) minute = 0
2) পুরো grid scan করে পচার-যোগ্য তাজা কমলা খুঁজে একসাথে পচাও
3) এই minute-এ কিছু পচলে minute += 1, ধাপ 2-এ ফেরো; না পচলে থামো
4) তাজা কমলা বাকি থাকলে -1, নাহলে minute
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতি minute-এ পুরো grid rescan করা মানে worst case প্রতিটা minute-এ O(m·n) কাজ, আর minute সংখ্যা O(m·n) হতে পারে — মোট O((m·n)^2)-এর দিকে। অথচ multi-source BFS প্রতিটা cell ঠিক একবার queue-তে ঢোকায় আর একবার বের করে, পচনের ঢেউ স্বাভাবিকভাবেই level ধরে এগোয় — মোট O(m·n)। rescan-এর অপচয়টাই মূল পার্থক্য।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **সব পচা কমলাকে একই সাথে BFS-এর source ধরো (minute 0), তারপর level সংখ্যাই মোট সময়।** আলাদা করে প্রতিটা পচা থেকে BFS চালানোর দরকার নেই — একটাই BFS, একগুচ্ছ start। আর শেষে তাজা কমলা গোনা থাকলে বুঝবে কেউ অপৌঁছনীয় ছিল।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রথমে grid scan করো: সব পচা কমলা queue-তে ঢোকাও (minute 0), আর তাজা কমলার সংখ্যা `fresh` গোনো। তারপর level-by-level BFS: প্রতি round-এ বর্তমান queue-র সব কমলা pop করে তাদের তাজা প্রতিবেশী পচাও (queue-তে যোগ করো, `fresh -= 1`)। round শেষ হলে `minutes += 1` (যদি কিছু পচে থাকে)। BFS শেষে `fresh == 0` হলে `minutes`, নাহলে `-1`। O(m·n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা পচা কমলা থেকে আলাদা করে দূরত্ব মাপব" বা "প্রতি minute-এ পুরো grid ঘুরব" না ভেবে ভাবো "সব পচা কমলাকে একসাথে queue-তে বসিয়ে দিই — এক BFS, ঢেউগুলো নিজেই মিলে যাবে, আর level-ই সময়।" বহু BFS / rescan থেকে নেমে এসো একটাই multi-source BFS-এ।
### ছবিতে বোঝা {#7-visual-explanation}
`grid = [[2,1,1],[1,1,0],[0,1,1]]` দিয়ে minute-by-minute:
```text
minute 0: minute 1: minute 2: minute 3: minute 4:
2 1 1 2 2 1 2 2 2 2 2 2 2 2 2
1 1 0 2 1 0 2 2 0 2 2 0 2 2 0
0 1 1 0 1 1 0 1 1 0 2 1 0 2 2
source (minute 0): শুধু (0,0)। ঢেউ ছড়ায় চার দিকে।
সব কমলা পচল minute 4-এ -> উত্তর 4
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`grid = [[2,1,1],[0,1,1],[1,0,1]]`:
1. scan: পচা `(0,0)` → queue। তাজা: `(0,1),(0,2),(1,1),(1,2),(2,0),(2,2)` → `fresh = 6`।
2. round 1: pop `(0,0)` → প্রতিবেশী `(0,1)` তাজা পচাও (`fresh=5`), `(1,0)=0` বাদ। `minutes=1`।
3. round 2: pop `(0,1)` → `(0,2)` পচাও (`fresh=4`), `(1,1)` পচাও (`fresh=3`)। `minutes=2`।
4. round 3: pop `(0,2),(1,1)` → `(1,2)` পচাও (`fresh=2`); `(2,1)=0`। `minutes=3`।
5. round 4: pop `(1,2)` → `(2,2)` পচাও (`fresh=1`)। `minutes=4`।
6. round 5: pop `(2,2)` → প্রতিবেশী সব পচা/0/বাইরে। কিছু পচল না।
7. queue খালি, কিন্তু `(2,0)` তাজা রয়ে গেল (`fresh = 1 > 0`) → return `-1`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
def oranges_rotting(grid):
R, C = len(grid), len(grid[0])
q = deque()
fresh = 0
# multi-source seeding: সব পচা কমলা minute 0-তে
for r in range(R):
for c in range(C):
if grid[r][c] == 2:
q.append((r, c))
elif grid[r][c] == 1:
fresh += 1
if fresh == 0: # পচানোর মতো কিছুই নেই
return 0
minutes = 0
while q:
# এই level-এ এখন যত পচা কমলা আছে, সবাইকে process করো
for _ in range(len(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 grid[nr][nc] == 1):
grid[nr][nc] = 2 # পচিয়ে দেওয়াই visited-marking
fresh -= 1
q.append((nr, nc)) # পরের ঢেউয়ের জন্য
if q: # এই round-এ নতুন কিছু পচল
minutes += 1
return minutes if fresh == 0 else -1 # বাকি তাজা থাকলে অপৌঁছনীয়
# ---- tests ----
g1 = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
g2 = [[2, 1, 1], [0, 1, 1], [1, 0, 1]]
g3 = [[0, 2]]
g4 = [[2, 2], [1, 1]]
assert oranges_rotting([row[:] for row in g1]) == 4
assert oranges_rotting([row[:] for row in g2]) == -1
assert oranges_rotting([row[:] for row in g3]) == 0 # তাজা কমলা নেই
assert oranges_rotting([row[:] for row in g4]) == 1
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- প্রথম double loop — সব পচা কমলা queue-তে (multi-source), আর তাজা কমলা `fresh`-এ গোনা।
- `if fresh == 0: return 0` — পচানোর মতো তাজা কমলাই নেই, সময় 0।
- `for _ in range(len(q))` — round শুরুর মুহূর্তে queue-তে যত কমলা, ঠিক ততটা pop; এটাই এক level সীমাবদ্ধ করে।
- `if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1` — bounds আগে, তারপর তাজা প্রতিবেশী।
- `grid[nr][nc] = 2` — পচানোই visited-marking; আলাদা set লাগে না, একই কমলা দুবার পচে না।
- `if q: minutes += 1` — round-এ নতুন কমলা যোগ হলেই minute বাড়ে; শেষ খালি round যেন বাড়তি minute না দেয়।
- `return minutes if fresh == 0 else -1` — সব পচলে সময়, নাহলে অপৌঁছনীয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`oranges_rotting(g1)`: একমাত্র source `(0,0)` থেকে ঢেউ চার level-এ সব কমলা পচায় → `4`। `g2`-তে `(2,0)` অপৌঁছনীয় থেকে যায় → `-1`। `g3`-এ তাজা কমলা নেই → `0`। `g4`-এ এক round-এ নিচের সারি পচে → `1`। সব assert pass, শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function orangesRotting(grid) {
const R = grid.length, C = grid[0].length;
let q = []; // BFS frontier (এক level)
let fresh = 0;
// multi-source seeding: সব পচা কমলা minute 0-তে
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (grid[r][c] === 2) q.push([r, c]);
else if (grid[r][c] === 1) fresh++;
}
}
if (fresh === 0) return 0; // পচানোর মতো কিছুই নেই
const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let minutes = 0;
while (q.length > 0) {
const next = []; // এই round-এ যারা নতুন পচল
for (const [r, c] of q) { // q = ঠিক এই minute-এর পচা কমলা
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === 1) {
grid[nr][nc] = 2; // পচিয়ে দেওয়াই visited-marking
fresh--;
next.push([nr, nc]); // পরের ঢেউয়ের জন্য
}
}
}
q = next;
if (q.length > 0) minutes++; // এই round-এ নতুন কিছু পচল
}
return fresh === 0 ? minutes : -1; // বাকি তাজা থাকলে অপৌঁছনীয়
}
const clone = (g) => g.map((row) => row.slice());
// ---- test cases ----
const g1 = [[2, 1, 1], [1, 1, 0], [0, 1, 1]];
const g2 = [[2, 1, 1], [0, 1, 1], [1, 0, 1]];
const g3 = [[0, 2]];
const g4 = [[2, 2], [1, 1]];
assert(orangesRotting(clone(g1)) === 4, "g1");
assert(orangesRotting(clone(g2)) === -1, "g2 অপৌঁছনীয়");
assert(orangesRotting(clone(g3)) === 0, "তাজা নেই");
assert(orangesRotting(clone(g4)) === 1, "এক round");
console.log("সব JS test pass!");
```
> **JS টীকা:** Python-এ `for _ in range(len(q))` দিয়ে level snapshot নেওয়া হয়; JS-এ এখানে আরও পরিষ্কার — পুরো বর্তমান `q`-এর উপর `for...of` চালিয়ে নতুন-পচা কমলাগুলো একটা আলাদা `next` array-তে জমিয়ে, `q = next` দিয়ে পরের minute-এ লাফ। এতে `shift()`-এর O(n) এড়ানো যায় আর level (minute) সীমা ঠিক থাকে। in-place `2` করে দেওয়াই visited-mark, আলাদা set লাগে না।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
type Grid = number[][];
function orangesRotting(grid: Grid): number {
const R = grid.length, C = grid[0].length;
let q: [number, number][] = [];
let fresh = 0;
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (grid[r][c] === 2) q.push([r, c]);
else if (grid[r][c] === 1) fresh++;
}
}
if (fresh === 0) return 0;
const dirs: [number, number][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let minutes = 0;
while (q.length > 0) {
const next: [number, number][] = [];
for (const [r, c] of q) {
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === 1) {
grid[nr][nc] = 2;
fresh--;
next.push([nr, nc]);
}
}
}
q = next;
if (q.length > 0) minutes++;
}
return fresh === 0 ? minutes : -1;
}
const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
const clone = (g: Grid): Grid => g.map((row) => row.slice());
const g1: Grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]];
const g2: Grid = [[2, 1, 1], [0, 1, 1], [1, 0, 1]];
const g3: Grid = [[0, 2]];
const g4: Grid = [[2, 2], [1, 1]];
expect(orangesRotting(clone(g1)) === 4, "4");
expect(orangesRotting(clone(g2)) === -1, "-1");
expect(orangesRotting(clone(g3)) === 0, "0");
expect(orangesRotting(clone(g4)) === 1, "1");
console.log("সব TS test pass!");
```
> **TS টীকা:** `q: [number, number][]` ও `dirs: [number, number][]` — tuple type নিশ্চিত করে queue ও direction-এ ঠিক `[row, col]` জোড়াই থাকে, তাই destructuring (`[r, c]`, `[dr, dc]`) type-safe। `type Grid = number[][]` cell value (0/1/2) সংখ্যা হিসেবে রাখে, তাই `=== 1`/`=== 2` তুলনা সঠিক type-এ হয়। return type `number` (`-1` সহ) স্পষ্ট।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(m · n)** — initial scan সব cell একবার; BFS-এ প্রতিটা cell বড়জোর একবার queue-তে ঢোকে ও বের হয়, প্রতিটা প্রতিবেশী constant-বার দেখা হয়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(m · n)** — worst case queue পুরো এক level (গ্রিড-আকারের) ধরে রাখতে পারে, যেমন প্রায় সব কমলা শুরুতেই পচা থাকলে। in-place পচানোয় আলাদা visited বাঁচে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- single-source ভেবে শুধু একটা পচা কমলা থেকে BFS — সব পচা কমলা একসাথে seed করতে হবে।
- শেষে `fresh` চেক না করা — অপৌঁছনীয় তাজা কমলা থাকলেও ভুল করে একটা সময় ফেরত দেওয়া।
- শেষ খালি round-এ `minutes` বাড়িয়ে এক বেশি গোনা — `if q:` দিয়ে রক্ষা করো, বা minute-কে cell-এর সাথে store করো।
- `len(q)` snapshot না নিয়ে loop-এর ভেতরে `q` বদলাতে থাকা — তাহলে level সীমা ভেঙে যায়; round শুরুতেই `len(q)` ধরো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: queue-র FIFO ([../../04-stack-and-queue/](../../04-stack-and-queue/README.md)) আর BFS level-expansion ([../bfs.md](../bfs.md))। এটা প্রথম **multi-source** BFS problem এই tracker-এ — single start থেকে নয়, একগুচ্ছ start থেকে একই ঢেউ। মূল শিক্ষা: "একসাথে ছড়ায় / nearest source পর্যন্ত সময়" মানেই queue-টা সব source দিয়ে শুরু করা — এক extra seeding লাইন, বাকি BFS অপরিবর্তিত। পরের ধাপ: একই multi-source idea-তে প্রতিটা cell-এর nearest 0-এর দূরত্ব (#9)।
### পরের অনুশীলন {#22-similar-harder-problems}
- 01 Matrix (প্রতিটা cell-এর nearest 0-এর দূরত্ব, multi-source) —