Problem link ও উৎস
- **Original source:** CSES Problem Set — Dynamic Programming section
- **Platform:** CSES —
- **Topic:** dynamic programming
- **Difficulty:** Medium
- **Pattern:** Grid DP + obstacles
- **Basic idea inherited from:** #7 Unique Paths — কিন্তু কিছু cell-এ ফাঁদ (trap), সেগুলো দিয়ে যাওয়া যায় না
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা `n × n` grid দেওয়া আছে। প্রতিটা cell হয় খালি (`.`) নয় ফাঁদ (`*`)। তুমি বাঁ-উপরের কোণ থেকে ডান-নিচের কোণে যেতে চাও, শুধু **ডানে** বা **নিচে** চলে। ফাঁদওয়ালা cell-এ পা রাখা যাবে না। কতগুলো আলাদা path আছে, গোনো — উত্তর `10^9 + 7` দিয়ে modulo।
```text
grid (3 x 3):
. . .
. * .
. . .
মাঝখানের ফাঁদ এড়িয়ে S থেকে E-তে যাওয়ার মোট 2 টা path
```
### Input ও output {#8-example-input-and-output}
```text
Input grid (3x3): Output: 2
. . .
. * .
. . .
Edge case 1: start cell নিজে ফাঁদ ('*' top-left) -> Output: 0
Edge case 2: কোনো ফাঁদ নেই (3x3 সব '.') -> Output: 6 (= Unique Paths)
Edge case 3: end cell ফাঁদ -> Output: 0
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো সেই শহরের block-grid, কিন্তু কিছু চৌরাস্তা বন্ধ (রাস্তা খোঁড়া)। তুমি পূর্ব-দক্ষিণে হেঁটে গন্তব্যে যাচ্ছ। যেকোনো খোলা চৌরাস্তায় পথ = পশ্চিম + উত্তরের পথ; কিন্তু চৌরাস্তা বন্ধ থাকলে সেখানে পৌঁছানোর পথই 0 — আর সেই 0 পরের চৌরাস্তাগুলোর হিসাবেও বয়ে যায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি সরাসরি #7 Unique Paths। সেখানে প্রতিটা cell-এর path = উপরের + বাঁয়ের। এখানে একটাই পরিবর্তন: cell-টা যদি ফাঁদ হয়, তার path-সংখ্যা **জোর করে 0** — সেখান দিয়ে কোনো path যেতে পারে না। বাকি সব structure অপরিবর্তিত।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic আগের মতোই: cell `(r, c)`-তে ঢোকার শেষ move উপর থেকে বা বাঁ থেকে, তাই path = দুই প্রতিবেশীর যোগ। কিন্তু একটা guard যোগ হয়: `(r, c)` যদি ফাঁদ হয়, তাহলে এই cell দিয়ে শূন্য path যায় (`dp[r][c] = 0`), যা downstream সব হিসাবেও সেই শূন্য ছড়িয়ে দেয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **2D array** `dp` (size `n × n`), `dp[r][c]` = start থেকে `(r, c)` পর্যন্ত valid path-এর সংখ্যা। সাথে আসল `grid` (কোথায় ফাঁদ জানতে)। চাইলে এক row রেখে O(n) space-এও করা যায়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State দুটো সংখ্যা: row আর column — তাই 2D array নিখুঁত, `dp[r][c]` cell-এর উত্তর ধরে। ফাঁদের তথ্যও 2D grid, তাই index মিলে যায়। Dependency শুধু উপরে আর বাঁয়ে, তাই row-by-row বাঁ-থেকে-ডান ভরলে নিরাপদ, আর এক row-তে compress করা যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা cell থেকে recurse করে দুই দিকের path যোগ — কিন্তু ফাঁদ বা grid-এর বাইরে গেলে 0।
```text
paths(r, c):
if r >= n or c >= n: return 0 # বাইরে
if grid[r][c] == '*': return 0 # ফাঁদ
if r == n-1 and c == n-1: return 1 # পৌঁছে গেছি
return paths(r+1, c) + paths(r, c+1)
answer = paths(0, 0)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই recursion **exponential** (প্রায় O(2^(2n))) — প্রতিটা cell দুই শাখা খোলে, আর মাঝের cell-গুলো বহু পথ দিয়ে বারবার গোনা হয় (overlapping subproblems)। CSES-এ n অনেক বড় (1000 পর্যন্ত), তাই এটা কার্যত কখনো শেষ হবে না।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **distinct cell মাত্র `n × n`-টা**, আর ফাঁদ শুধু কিছু cell-কে 0 বানায়। প্রতিটা cell-এর path একবার গুনে রাখলে O(n^2)-এ কাজ শেষ; ফাঁদ handle করা মানে শুধু সেই cell-এ 0 বসিয়ে দেওয়া।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[r][c]` = start `(0,0)` থেকে cell `(r, c)` পর্যন্ত পৌঁছানোর valid path-এর সংখ্যা (ফাঁদ এড়িয়ে)।
**Transition:**
```text
if grid[r][c] == '*': dp[r][c] = 0 # ফাঁদ: কোনো path নেই
else: dp[r][c] = dp[r-1][c] + dp[r][c-1] # উপর + বাঁ
```
(grid-এর বাইরের প্রতিবেশীকে 0 ধরা হয়।)
**Base case:** `dp[0][0] = 1` যদি start ফাঁদ না হয়, নয়তো `0`।
**Answer location:** `dp[n-1][n-1]`। বড় উত্তরে প্রতি যোগে `% (10**9 + 7)`।
Memoization (top-down): উপরের `paths(r,c)` recursion-টাই রাখো, dict যোগ করো। Tabulation (bottom-up): row-by-row বাঁ-থেকে-ডান ভরো, ফাঁদ cell-এ 0। শুধু আগের row লাগে বলে এক row-তে compress করা যায়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** Unique Paths-কে নতুন করে শেখার দরকার নেই — শুধু একটা guard বসাও: "এই cell কি ফাঁদ? হলে 0।" এটাই DP-র একটা সাধারণ কৌশল: একটা পরিচিত recurrence-এর উপর একটা ছোট constraint চাপানো। কঙ্কাল এক, শুধু একটা if যোগ।
### ছবিতে বোঝা {#7-visual-explanation}
`dp[r][c]` = `(r,c)`-তে পৌঁছানোর path। `*` = ফাঁদ। 3×3 grid, মাঝে ফাঁদ:
```text
grid : dp ভরা:
. . . c=0 c=1 c=2
. * . r=0 1 1 1
. . . r=1 1 0 1 <- (1,1) ফাঁদ, তাই 0
r=2 1 1 2
dp[0][*] = 1, dp[*][0] = 1 (প্রথম row/column, ফাঁদ না থাকলে)
dp[1][1] = ফাঁদ -> 0
dp[1][2] = dp[0][2] + dp[1][1] = 1 + 0 = 1
dp[2][1] = dp[1][1] + dp[2][0] = 0 + 1 = 1
dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2 <- answer
ফাঁদের 0 দুদিকে ছড়িয়ে path কমিয়ে দিল: 6 থেকে 2।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
3×3 grid, মাঝে ফাঁদ, tabulation, modulo ছাড়া (ছোট মান):
1. প্রথম row: `dp[0] = [1, 1, 1]` (কোনো ফাঁদ নেই)
2. প্রথম column: `dp[0][0]=dp[1][0]=dp[2][0]=1`
3. dp[1][1]: ফাঁদ → 0
4. dp[1][2] = dp[0][2] + dp[1][1] = 1 + 0 = 1
5. dp[2][1] = dp[1][1] + dp[2][0] = 0 + 1 = 1
6. dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2 → answer
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
MOD = 10**9 + 7
# ---- way 1: memoization (top-down) ----
def grid_paths_memo(grid):
n = len(grid)
memo = {}
def paths(r, c):
if r < 0 or c < 0:
return 0
if grid[r][c] == '*': # ফাঁদ
return 0
if r == 0 and c == 0: # start (ফাঁদ না হলে এখানে আসে)
return 1
if (r, c) in memo:
return memo[(r, c)]
memo[(r, c)] = (paths(r - 1, c) + paths(r, c - 1)) % MOD
return memo[(r, c)]
if grid[0][0] == '*' or grid[n - 1][n - 1] == '*':
return 0
return paths(n - 1, n - 1)
# ---- way 2: tabulation (bottom-up) ----
def grid_paths_tab(grid):
n = len(grid)
if grid[0][0] == '*':
return 0
dp = [[0] * n for _ in range(n)]
dp[0][0] = 1
for r in range(n):
for c in range(n):
if grid[r][c] == '*':
dp[r][c] = 0
continue
if r == 0 and c == 0:
continue # base, already 1
up = dp[r - 1][c] if r > 0 else 0
left = dp[r][c - 1] if c > 0 else 0
dp[r][c] = (up + left) % MOD
return dp[n - 1][n - 1]
# ---- tests ----
cases = [
([list("..."), list(".*."), list("...")], 2),
([list("..."), list("..."), list("...")], 6), # ফাঁদ নেই = Unique Paths 3x3
([list("*.."), list("..."), list("...")], 0), # start ফাঁদ
([list("..."), list("..."), list("..*")], 0), # end ফাঁদ
([list("."), ], 1), # 1x1 খালি
([list("*"), ], 0), # 1x1 ফাঁদ
([list(".*"), list("..")], 1), # 2x2, উপর-ডানে ফাঁদ
]
for grid, want in cases:
assert grid_paths_memo(grid) == want, (grid, grid_paths_memo(grid))
assert grid_paths_tab(grid) == want, (grid, grid_paths_tab(grid))
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `grid_paths_memo`: `paths(r,c)` valid path-সংখ্যা দেয়; বাইরে বা ফাঁদ → 0; start → 1; `memo` repeated কাজ এড়ায়; শুরুতেই start/end ফাঁদ হলে সরাসরি 0।
- `grid_paths_tab`: `dp[0][0]=1` base; প্রতি cell-এ ফাঁদ হলে 0 আর `continue`; নয়তো উপর+বাঁ (সীমানার বাইরে 0 ধরে) `% MOD`; answer `dp[n-1][n-1]`।
- দুই version-ই একই guard — ফাঁদ মানে 0 — শুধু একটা recursion-চালিত, একটা loop-চালিত।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ সাতটা grid: মাঝে-ফাঁদ (2), ফাঁদহীন (6 = Unique Paths), start-ফাঁদ (0), end-ফাঁদ (0), 1×1 খালি (1), 1×1 ফাঁদ (0), আর একটা 2×2 যেখানে একটাই path বাঁচে (1)। প্রতিটার জন্য দুই function মিলতে হবে। সব pass হলে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
- Memoization ও tabulation: **O(n^2)** — প্রতিটা cell একবার করে। (Naive recursion ছিল প্রায় O(2^(2n))।)
### অতিরিক্ত জায়গা {#19-space-complexity}
- Memoization: **O(n^2)** — dict + recursion stack।
- Tabulation: **O(n^2)** — 2D array।
(এক row rolling করলে O(n) space-ও সম্ভব, ফাঁদ-cell-এ সেই ঘর 0 করে দিয়ে।)
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- ফাঁদ cell-এ 0 না বসিয়ে শুধু skip করা — তখন পুরোনো garbage মান থেকে যায়, ভুল গণনা।
- start বা end নিজে ফাঁদ — এই case আলাদা না ধরলে ভুল 1 ফেরত আসতে পারে; শুরুতেই check করো।
- modulo নিতে ভুলে যাওয়া — CSES-এ বড় grid-এ উত্তর বিশাল, modulo ছাড়া wrong answer।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: #7 Unique Paths-এর grid counting, একটা ফাঁদ-guard যোগ করা। [../state-transition-thinking.md](../state-transition-thinking.md)-এর "Problem 4 — Grid Paths" section-এ obstacle version-এর কথা সরাসরি বলা ("cell-টা blocked হলে `dp[r][c] = 0`")।
### পরের অনুশীলন {#22-similar-harder-problems}
- Minimum Path Sum (counting-এর বদলে min cost) —