Problem link ও উৎস
- **Original source:** Classic BFS flood-fill exercise
- **Platform:** LeetCode —
- **Topic:** queue (BFS frontier)
- **Difficulty:** Medium
- **Pattern:** BFS frontier — queue
- **Basic idea inherited from:** সাধারণ queue discipline; পূর্ণ graph theory [../../09-graphs/](../../09-graphs/README.md)-এ
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা grid দেওয়া আছে, যার প্রতিটা ঘর হয় `'1'` (স্থল) নয় `'0'` (পানি)। পাশাপাশি (উপর-নিচ-ডান-বাঁ, তির্যক নয়) লেগে থাকা স্থলের ঘরগুলো মিলে একটা **দ্বীপ** বানায়। কয়টা আলাদা দ্বীপ আছে, গুনে বলো।
```text
grid:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
-> 3 দ্বীপ (উপরের-বাঁয়ের block, মাঝের একক ঘর, নিচের-ডানের জোড়া)
```
### Input ও output {#8-example-input-and-output}
```text
Input :
[["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]] -> Output: 1
Input :
[["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]] -> Output: 3
Edge case 1 (পুরো পানি) : [["0"]] -> 0
Edge case 2 (একক স্থল) : [["1"]] -> 1
Edge case 3 (খালি grid) : [] -> 0
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা সাদা কাগজে কালি ফেলার মতো ভাবো। একটা স্থল-ঘরে এক ফোঁটা কালি ফেললে, সেটা চারপাশের লাগোয়া স্থল-ঘরে ছড়ায়, তারপর তাদের লাগোয়া ঘরে — পানির ঘরে গিয়ে থেমে যায়। এক ফোঁটায় ভিজে যাওয়া পুরো অংশটাই এক দ্বীপ। শুকনো (এখনো-না-ভেজা) আরেকটা স্থল-ঘর পেলে নতুন ফোঁটা — নতুন দ্বীপ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **BFS frontier (queue)** pattern-এর সরাসরি প্রয়োগ। মূল idea — একটা শুরুর ঘর থেকে ring-এ ring-এ বাইরের দিকে ছড়িয়ে পুরো connected অংশ "ভরে ফেলা" (flood fill)। এই chapter শুধু queue-টা ঠিকঠাক চালাতে শেখায়; দ্বীপ গোনা, connectivity, traversal-এর পূর্ণ তত্ত্ব থাকে [../../09-graphs/](../../09-graphs/README.md)-এ। এখানে grid-ই আমাদের graph, প্রতিটা স্থল-ঘর একটা node, পাশাপাশি স্থল-ঘরের মধ্যে edge।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **connected components গোনা**। পুরো grid scan করো; যখনই একটা না-দেখা স্থল-ঘর পাও, সেটা একটা নতুন দ্বীপের সূচনা — counter এক বাড়াও — তারপর BFS দিয়ে সেই দ্বীপের *সব* ঘর খুঁজে `visited` mark করে দাও, যাতে একই দ্বীপ আবার গোনা না হয়। scan শেষ হলে counter-ই উত্তর।
correctness-এর চাবি: একবার BFS পুরো component-টা নিঃশেষ করে ফেলে, তাই বাইরের loop প্রতিটা component-কে ঠিক একবার করে "নতুন" হিসেবে পায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **queue** (`Python`-এ `collections.deque`) BFS frontier ধরে রাখতে। সাথে একটা `visited` 2D array (বা grid নিজেই mutate করা) যাতে কোনো ঘর দুবার process না হয়। queue-তে আমরা ঘরের `(row, col)` জোড়া রাখি।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
flood fill মানে "একটা ঘর থেকে শুরু করে তার সব প্রতিবেশী, তারপর তাদের প্রতিবেশী..." — একটা frontier ক্রমে বাইরের দিকে এগোয়। queue-এর FIFO order ঠিক এই ring-by-ring সম্প্রসারণ দেয়: যাকে আগে আবিষ্কার করেছি, তার প্রতিবেশী আগে explore হয়। `deque`-এর `append` আর `popleft` দুটোই O(1)। (দ্বীপ গোনার জন্য DFS-ও চলত, কিন্তু এই chapter queue-discipline practice করাচ্ছে।)
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তাটাও আসলে এটাই — grid scan করো, একটা না-দেখা স্থল পেলে কোনো traversal (BFS বা DFS) দিয়ে গোটা component mark করো, count বাড়াও। "brute force" বলতে যা এড়াতে চাই তা হলো connectivity-র **আরও খারাপ** উপায়: যেমন প্রতিটা স্থল-জোড়ার মধ্যে আলাদা করে পথ আছে কিনা বারবার যাচাই করা।
```text
প্রতিটা স্থল-ঘর থেকে অন্য প্রতিটা স্থল-ঘরে পথ আছে কিনা খুঁজি -> খুবই অপচয়
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা স্থল-ঘরের জন্য বারবার অন্যদের সাথে connectivity যাচাই করলে কাজটা ঘরের সংখ্যার বর্গে চলে যায়, কারণ একই ঘর বহুবার পুনরায় explore হয়। flood-fill-এ প্রতিটা ঘর ঠিক একবার visited হয়, তাই কাজ grid-এর আকারের সমানুপাতিক — **O(rows × cols)**।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: একবার কোনো দ্বীপের একটা ঘর পেলে, সেই দ্বীপের *বাকি সব* ঘর একটানা BFS-এ পাওয়া যায় — আলাদা করে খোঁজার দরকার নেই। তাই বাইরের scan শুধু "নতুন দ্বীপের প্রথম ঘর" ধরার কাজ করে, আর গোনাটা সেখানেই ঘটে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
grid-এর প্রতিটা ঘর scan করো। স্থল আর না-দেখা হলে: count এক বাড়াও, ঘরটা queue-তে দাও আর visited mark করো; তারপর queue খালি না হওয়া পর্যন্ত popleft করে চার প্রতিবেশী দেখো — যেটা grid-এর ভেতরে, স্থল আর না-দেখা, তাকে visited mark করে enqueue করো। **push করার সময়েই** visited mark করা জরুরি, যাতে একই ঘর queue-তে দুবার না ঢোকে।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** grid-টাকে আলাদা ঘরের জাল না ভেবে একটা **graph** ভাবো — প্রতিটা স্থল-ঘর node, পাশাপাশি স্থল-ঘরের মধ্যে edge। তখন "কয়টা দ্বীপ" প্রশ্নটা পরিণত হয় ক্লাসিক "কয়টা connected component" প্রশ্নে, আর উত্তরটা একটা সাধারণ BFS sweep।
### ছবিতে বোঝা {#7-visual-explanation}
ছোট grid `[["1","1","0"],["0","1","0"],["0","0","1"]]`-এ BFS frontier:
```text
grid (r,c): scan এসে প্রথম '1' (0,0) -> দ্বীপ #1 শুরু, BFS:
1 1 0 queue=[(0,0)] pop(0,0) -> প্রতিবেশী (0,1),(1,0)? (1,0)='0'
0 1 0 enqueue (0,1) pop(0,1) -> প্রতিবেশী (1,1)='1' enqueue
0 0 1 pop(1,1) -> প্রতিবেশী সব visited/পানি -> দ্বীপ #1 শেষ
visited: (0,0),(0,1),(1,1)
scan এগোয় -> পরের না-দেখা '1' হলো (2,2) -> দ্বীপ #2 শুরু, BFS:
queue=[(2,2)] pop -> কোনো স্থল-প্রতিবেশী নেই -> দ্বীপ #2 শেষ
মোট দ্বীপ = 2
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[["1","0"],["0","1"]]`:
1. scan `(0,0)` — `'1'`, না-দেখা → দ্বীপ #1, `count = 1`; BFS: enqueue `(0,0)`, mark visited
2. pop `(0,0)` — প্রতিবেশী `(0,1)='0'`, `(1,0)='0'` — কেউ স্থল নয় → দ্বীপ #1 শেষ
3. scan `(0,1)` — `'0'`, এড়িয়ে যাও
4. scan `(1,0)` — `'0'`, এড়িয়ে যাও
5. scan `(1,1)` — `'1'`, না-দেখা → দ্বীপ #2, `count = 2`; BFS: pop `(1,1)`, স্থল-প্রতিবেশী নেই → শেষ
6. scan শেষ → return `2`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
def num_islands(grid):
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
visited = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1' and not visited[r][c]:
count += 1 # নতুন দ্বীপ পেলাম
queue = deque([(r, c)])
visited[r][c] = True
while queue:
cr, cc = queue.popleft() # FIFO frontier
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = cr + dr, cc + dc
if (0 <= nr < rows and 0 <= nc < cols
and grid[nr][nc] == '1' and not visited[nr][nc]):
visited[nr][nc] = True # push করার সময়েই mark
queue.append((nr, nc))
return count
# ---- tests ----
g1 = [["1", "1", "1", "1", "0"],
["1", "1", "0", "1", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "0", "0", "0"]]
assert num_islands(g1) == 1
g2 = [["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]]
assert num_islands(g2) == 3
assert num_islands([["0"]]) == 0 # পুরো পানি
assert num_islands([["1"]]) == 1 # একক স্থল
assert num_islands([]) == 0 # খালি grid
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not grid or not grid[0]: return 0` — খালি grid-এ দ্বীপ নেই।
- `visited = [[False]*cols ...]` — কোন ঘর process হয়ে গেছে তার হিসাব; grid mutate এড়াতে আলাদা array।
- `if grid[r][c] == '1' and not visited[r][c]:` — নতুন দ্বীপের প্রথম ঘর; এখানেই `count += 1`।
- `queue = deque([(r, c)])` / `visited[r][c] = True` — BFS শুরু; শুরুর ঘর সাথে সাথে visited।
- `cr, cc = queue.popleft()` — FIFO; frontier ring-by-ring বাইরে ছড়ায়।
- ভেতরের `if (...)` — প্রতিবেশী grid-এর সীমার ভেতরে, স্থল, না-দেখা হলেই গ্রহণ; `visited` mark `append`-এর ঠিক আগে যাতে duplicate না হয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`num_islands(g2)` → scan উপরের-বাঁয়ের `2×2` block পেয়ে দ্বীপ #1 (BFS পুরো block ভরে), মাঝের একক ঘরে দ্বীপ #2, নিচের-ডানের জোড়ায় দ্বীপ #3 → `3`। `num_islands([["0"]])` → কোনো স্থল নেই, count `0`। সব assert pass করে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(rows × cols)** — প্রতিটা ঘর বাইরের scan-এ একবার দেখা হয়, আর BFS-এ বড়জোর একবার enqueue/dequeue হয়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(rows × cols)** — `visited` array পুরো grid-এর সমান; queue-ও সবচেয়ে খারাপ ক্ষেত্রে (পুরো grid স্থল) এতটা বড় হতে পারে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- ঘর dequeue করার সময় visited mark করা — তখন একই ঘর queue-তে একাধিকবার ঢুকে যায়; mark করতে হয় **enqueue-এর সময়**।
- সীমানা check বাদ দেওয়া — `0 <= nr < rows and 0 <= nc < cols` না থাকলে grid-এর বাইরে index করে crash।
- তির্যক প্রতিবেশী যোগ করা — এই problem-এ শুধু 4-দিক (উপর-নিচ-ডান-বাঁ) connectivity।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: queue-র FIFO discipline (BFS frontier)। chapter-এর [../patterns.md](../patterns.md)-এর Pattern 2 (BFS Frontier) এখানে সরাসরি; connected-component, grid-as-graph, traversal-এর পূর্ণ আলোচনা [../../09-graphs/](../../09-graphs/README.md)-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Rotting Oranges (multi-source BFS) —