Skip to content

008 — Grid Paths

Source

  • Original source: CSES Problem Set — Dynamic Programming section
  • Platform: CSES — https://cses.fi/problemset/task/1638
  • Topic: dynamic programming
  • Difficulty: Medium
  • Pattern: Grid DP + obstacles
  • Basic idea inherited from: #7 Unique Paths — কিন্তু কিছু cell-এ ফাঁদ (trap), সেগুলো দিয়ে যাওয়া যায় না

1. Problem in simple words

একটা n × n grid দেওয়া আছে। প্রতিটা cell হয় খালি (.) নয় ফাঁদ (*)। তুমি বাঁ-উপরের কোণ থেকে ডান-নিচের কোণে যেতে চাও, শুধু ডানে বা নিচে চলে। ফাঁদওয়ালা cell-এ পা রাখা যাবে না। কতগুলো আলাদা path আছে, গোনো — উত্তর 10^9 + 7 দিয়ে modulo।

grid (3 x 3):
    . . .
    . * .
    . . .
মাঝখানের ফাঁদ এড়িয়ে S থেকে E-তে যাওয়ার মোট 2 টা path

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 করা যায়।

6. Real-life analogy

ভাবো সেই শহরের block-grid, কিন্তু কিছু চৌরাস্তা বন্ধ (রাস্তা খোঁড়া)। তুমি পূর্ব-দক্ষিণে হেঁটে গন্তব্যে যাচ্ছ। যেকোনো খোলা চৌরাস্তায় পথ = পশ্চিম + উত্তরের পথ; কিন্তু চৌরাস্তা বন্ধ থাকলে সেখানে পৌঁছানোর পথই 0 — আর সেই 0 পরের চৌরাস্তাগুলোর হিসাবেও বয়ে যায়।

7. Visual explanation

dp[r][c] = (r,c)-তে পৌঁছানোর path। * = ফাঁদ। 3×3 grid, মাঝে ফাঁদ:

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।

8. Example input and output

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

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা cell থেকে recurse করে দুই দিকের path যোগ — কিন্তু ফাঁদ বা grid-এর বাইরে গেলে 0।

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:

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 যোগ।

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

15. Python solution

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-চালিত।

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!।

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।

21. Which basic problem this inherits from

ভিত্তি: #7 Unique Paths-এর grid counting, একটা ফাঁদ-guard যোগ করা। ../state-transition-thinking.md-এর "Problem 4 — Grid Paths" section-এ obstacle version-এর কথা সরাসরি বলা ("cell-টা blocked হলে dp[r][c] = 0")।

22. Similar harder problems

23. Pattern learned

Grid DP with obstacles: পরিচিত grid recurrence (উপর + বাঁ) নাও, তারপর blocked cell-এ dp = 0 বসিয়ে constraint চাপাও। সেই 0 downstream-এ আপনিই ছড়ায়। "পরিচিত recurrence + ছোট guard" — DP-তে বহুবার লাগবে।

24. Final summary

ভবিষ্যতের আমাকে: "Grid Paths = Unique Paths + একটা if (ফাঁদ হলে 0)।" State dp[r][c] = (r,c)-তে valid path, transition উপর+বাঁ কিন্তু ফাঁদ-এ 0, base dp[0][0]=1 (ফাঁদ না হলে), modulo নিতে ভুলো না। মনে রেখো: একটা constraint প্রায়ই মানে একটা পরিচিত DP-তে একটা ছোট guard বসানো।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।