Problem link ও উৎস
- **Original source:** Classic capstone interview problem (grid flood fill)
- **Platform:** LeetCode —
- **Topic:** graphs + recursion (DFS)
- **Difficulty:** Medium
- **Pattern:** Grid flood fill — connected-component counting via DFS
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **09 graphs** (grid-টাকে একটা implicit graph ধরা: প্রতিটা land cell একটা node, পাশের land cell-এর সাথে edge; connected component গোনা) আর **06 recursion** (DFS দিয়ে একটা cell থেকে শুরু করে পুরো island ছেয়ে ফেলা — flood fill)। দুই tool জোড়া লাগলেই এই problem।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা grid (সারি-কলামের ছক) দেওয়া, যেখানে প্রতিটা ঘর হয় `'1'` (স্থল/land) নয় `'0'` (জল/water)। পাশাপাশি (উপর-নিচ-বাঁ-ডান, তির্যক না) থাকা land ঘরগুলো মিলে একটা **island** বানায়। তোমার কাজ: grid-এ মোট কতগুলো আলাদা island আছে গোনো।
```text
grid:
1 1 0 0
1 1 0 0
0 0 1 0
0 0 0 1
island সংখ্যা = 3 (উপরে-বাঁয়ে একটা, মাঝে একটা, নিচে-ডানে একটা)
```
### Input ও output {#8-example-input-and-output}
```text
Input :
1 1 0 0
1 1 0 0
0 0 1 0
0 0 0 1
Output: 3
Edge case 1 (পুরো জল): সব '0' -> Output: 0
Edge case 2 (পুরো ডাঙা 1x3): 1 1 1 -> Output: 1
Edge case 3 (খালি grid): [] -> Output: 0
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা মানচিত্রে কালি ছড়ানো। তুমি একটা শুকনো ডাঙায় এক ফোঁটা রঙ ফেললে — রঙ চারদিকে যত দূর ডাঙা আছে ততদূর ছড়িয়ে পুরো দ্বীপটা রাঙিয়ে দেয়, জল পেলে থেমে যায়। একটা দ্বীপ পুরো রাঙানো হলে তুমি এগিয়ে যাও পরের না-রাঙানো ডাঙা খুঁজতে — যতবার নতুন ফোঁটা ফেলতে হলো, ততগুলো দ্বীপ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem দুটো আগের chapter-এর tool জোড়া দেয়:
- **09 graphs** থেকে: grid-টা আসলে একটা লুকানো graph — প্রতিটা land cell একটা node, পাশের land cell-এর সাথে edge। তখন "কতগুলো island" = "কতগুলো connected component"।
- **06 recursion** থেকে: একটা land cell পেলে DFS দিয়ে তার চারপাশের সব যুক্ত land cell-এ ছড়িয়ে গিয়ে পুরো island-টা "ভিজিয়ে" (flood fill) ফেলা।
একা graph-চিন্তা দেয় component-counting framing; একা recursion দেয় ছড়িয়ে পড়ার কৌশল। দুটো মিললে পরিষ্কার flood fill।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **connected components গোনা**। প্রতিটা নতুন, এখনও-না-ছোঁয়া land cell একটা নতুন component-এর প্রতিনিধি। সেখান থেকে DFS করে পুরো component-কে "visited" চিহ্নিত করলে, পরে সেই cell-গুলো আর নতুন island শুরু করতে পারবে না। তাই কতবার আমরা নতুন DFS শুরু করি = island-এর সংখ্যা।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
মূল tool: **DFS recursion** (06)। আলাদাভাবে visited চিহ্ন রাখতে হয় — হয় একটা আলাদা `visited` set/matrix, নয় (এখানে যেমন) ভিজিয়ে ফেলা cell-কে সরাসরি `'0'` করে দেওয়া (in-place marking)। implicit graph-টা নিজেই data structure (09)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
grid-এ adjacency সরাসরি index দিয়ে পাওয়া যায় (`r±1`, `c±1`) — আলাদা adjacency list বানাতে হয় না, তাই DFS recursion-ই সবচেয়ে সহজ ও স্বাভাবিক tool। একটা cell ভিজিয়ে `'0'` করে দিলে সেটা আর গোনায় আসে না, তাই আলাদা visited structure-ও বাঁচে। এই in-place flood fill-ই recursion (06) আর grid-graph (09)-কে এখানে নিখুঁত করে তোলে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
আসলে এই problem-এর "brute force"-ও একটা traversal-ই — কিন্তু সরল চিন্তা হলো: প্রতিটা cell ঘুরে দেখি, land পেলে তার চারপাশের সব যুক্ত land-কে আলাদা একটা `visited` set-এ চিহ্নিত করি, আর নতুন (অচিহ্নিত) land পেলেই counter বাড়াই।
```text
visited = set()
count = 0
for প্রতিটা cell (r, c):
if grid[r][c] == '1' and (r,c) not in visited:
count += 1
dfs(r, c) # যুক্ত সব land visited-এ ঢোকাও
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা আসলে সঠিক ও যথেষ্ট দ্রুত (O(rows·cols)) — flood-fill problem-এ নিখুঁত brute force আর optimal প্রায় একই। "ধীর" version বলতে: যদি প্রতিটা cell থেকে বারবার পুরো grid ঘুরে যুক্ততা যাচাই করতে যেতাম (visited চিহ্ন না রেখে), তখন একই cell বহুবার দেখা হয়ে খরচ ফুলে যেত। visited-marking (বা in-place `'0'`) সেই পুনরাবৃত্তি ঠেকায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একটা island একবার পুরো ভিজিয়ে ফেললে, তার কোনো cell আর নতুন island শুরু করতে পারে না।** তাই শুধু গুনে রাখলেই হয় — কতবার আমরা একটা টাটকা (এখনও `'1'`) cell-এ DFS শুরু করি। এই এক চিন্তাই counting-টা সহজ করে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
পুরো grid scan করো। যখনই একটা `'1'` পাও যা এখনও ভেজানো হয়নি: island counter এক বাড়াও, আর সেখান থেকে DFS করে চারদিকের সব যুক্ত `'1'`-কে `'0'` করে দাও (ভিজিয়ে দাও)। scan শেষ হলে counter-ই island-সংখ্যা। in-place `'0'`-করা মানে আলাদা visited লাগে না।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কোন cell কোন cell-এর সাথে যুক্ত তার পুরো map বানাব" ভাবার বদলে ভাবো "land পেলেই এক ফোঁটা রঙ ফেলে পুরো island মুছে দিই (`'0'` করি), আর কতবার ফোঁটা ফেলতে হলো গুনি।" component-counting একটা scan + flood fill-এ গলে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
ছোট grid-এ flood fill, `X` = এইমাত্র ভেজানো (`'0'` করা):
```text
শুরু: (0,0)-তে '1' পেলাম -> DFS শুরু, island গোনা = 1
1 1 0 X 1 0 X X 0 X X 0
1 0 0 -> 1 0 0 -> X 0 0 -> X 0 0 (এই island শেষ)
0 0 1 0 0 1 0 0 1 0 0 1
তারপর scan চলতে চলতে (2,2)-তে আরেকটা '1' -> DFS শুরু, island গোনা = 2
শেষ উত্তর = 2
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input grid `[["1","1"],["0","1"]]`:
1. scan `(0,0)='1'` → count = 1; DFS: `(0,0)→'0'`, ডানে `(0,1)='1'→'0'`, তার নিচে `(1,1)='1'→'0'`; চারপাশ আর `'1'` নেই → island শেষ
2. scan `(0,1)` এখন `'0'` → skip
3. scan `(1,0)='0'` → skip
4. scan `(1,1)` এখন `'0'` → skip
5. শেষ → return `count = 1`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def num_islands(grid):
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
def dfs(r, c):
# সীমার বাইরে বা জল হলে থামো
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
return
grid[r][c] = "0" # এই land ভিজিয়ে দাও (visited)
dfs(r + 1, c) # নিচ
dfs(r - 1, c) # উপর
dfs(r, c + 1) # ডান
dfs(r, c - 1) # বাঁ
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1": # টাটকা land -> নতুন island
count += 1
dfs(r, c) # পুরো island ভিজিয়ে দাও
return count
# ---- tests ----
g1 = [["1","1","0","0"],
["1","1","0","0"],
["0","0","1","0"],
["0","0","0","1"]]
assert num_islands(g1) == 3
assert num_islands([["0","0"],["0","0"]]) == 0 # পুরো জল
assert num_islands([["1","1","1"]]) == 1 # একটানা ডাঙা
assert num_islands([]) == 0 # খালি grid
assert num_islands([["1","0","1","0","1"]]) == 3 # বিচ্ছিন্ন ডাঙা
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not grid or not grid[0]: return 0` — খালি grid edge case।
- `rows, cols = ...` — সীমা ধরে রাখি, যাতে DFS-এ index-চেক করা যায়।
- `def dfs(r, c)` — recursive flood fill (06 recursion)।
- `if ... or grid[r][c] != "1": return` — boundary-র বাইরে গেলে বা জল/already-ভেজানো পেলে থামো — এটাই DFS-এর base case।
- `grid[r][c] = "0"` — এই cell ভিজিয়ে দাও, যাতে আবার গোনা না হয় (in-place visited)।
- চারটা `dfs(...)` — চার প্রতিবেশীতে ছড়াও (grid-graph-এর edge, 09)।
- বাইরের double loop — প্রতিটা cell scan; টাটকা `'1'` পেলে count বাড়িয়ে নতুন DFS।
- `return count` — মোট কতবার নতুন DFS শুরু হলো = island-সংখ্যা।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`g1`-এ scan করতে করতে প্রথম `'1'` `(0,0)`-তে → count 1, DFS উপরে-বাঁয়ের 2x2 ব্লক মুছে দেয়; পরে `(2,2)`-তে → count 2, একক cell মুছে যায়; শেষে `(3,3)`-তে → count 3। return 3 — assert pass। পুরো-জল, একটানা-ডাঙা, খালি, বিচ্ছিন্ন case-ও সঠিক। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(rows · cols)** — প্রতিটা cell সর্বোচ্চ একবার scan-এ আর একবার DFS-এ ছোঁয়া হয়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(rows · cols)** worst case — recursion stack পুরো grid land হলে তত গভীর হতে পারে (06 recursion-এর hidden cost)। in-place marking-এ আলাদা visited লাগে না, তবু stack-টা থাকে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- ভেজানো cell চিহ্নিত না করা (`'0'` না করা বা visited-এ না ঢোকানো) — তখন DFS অসীম লুপে পড়ে বা একই island বহুবার গোনে।
- তির্যক (diagonal) প্রতিবেশীও যুক্ত ধরা — এই problem-এ শুধু 4-direction; 8-direction ভুল উত্তর দেয়।
- boundary-চেক DFS-এর শুরুতে না রাখা — তখন index out of range crash।
- খালি grid (`[]`) আলাদা না ভাবা — `grid[0]`-এ crash করতে পারে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: graph-এ connected component / DFS traversal (09 graphs, [../../09-graphs/](../../09-graphs/README.md)) + recursion দিয়ে নিজেকে চার দিকে ডাকা (06 recursion, [../../06-recursion-and-backtracking/](../../06-recursion-and-backtracking/README.md))। সাধারণ graph DFS-ই এখানে grid-এর উপর implicit-edge দিয়ে চলছে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Max Area of Island (একই flood fill, কিন্তু area গোনো) —