Skip to content

010 — Labyrinth

Source

  • Original source: CSES Problem Set — Graph Algorithms
  • Platform: CSES — https://cses.fi/problemset/task/1193
  • Topic: graphs
  • Difficulty: Medium (competitive-programming scale)
  • Pattern: grid BFS + shortest-path reconstruction via parent pointers
  • Basic idea inherited from: BFS levels / shortest path (../bfs.md); queue (../../04-stack-and-queue/)

1. Problem in simple words

তোমাকে একটা গোলকধাঁধা (maze) দেওয়া আছে n x m grid হিসেবে: # দেয়াল, . খালি পথ, A শুরুর জায়গা, B গন্তব্য। তুমি চার দিকে (উপর-নিচ-বাম-ডান) এক ধাপ করে হাঁটতে পারো, দেয়াল ভেদ করা যায় না। বলো: A থেকে B-তে পৌঁছানো সম্ভব কিনা; সম্ভব হলে সবচেয়ে কম কত ধাপ লাগে, আর সেই পথটা U/D/L/R (up/down/left/right) অক্ষরের একটা string হিসেবে ফেরত দাও।

maze:
  # # # # #
  # A . . #
  # # . # #
  # . B . #     <- A থেকে B-তে সবচেয়ে ছোট পথ আছে
  # # # # #

2. Which basic idea does this inherit from?

মূল ভিত হলো BFS দিয়ে shortest path (../bfs.md)। unweighted graph-এ (প্রতিটা ধাপের cost সমান) BFS কোনো cell-কে প্রথমবার যখন ছোঁয়, তখনই তার একটা shortest path পাওয়া হয়ে যায় — এটাই সেই defend-করার থিওরেম। এখানে grid-টা implicit graph: প্রতিটা খালি cell একটা node, পাশাপাশি দুই খালি cell-এর মধ্যে edge। নতুন উপাদান: শুধু দূরত্ব নয়, আসল পথটা চাই — তাই BFS-এর সাথে parent-pointer যোগ করতে হবে।

3. What is the hidden math or logic?

লুকানো logic দুই স্তরে:

প্রথমত, BFS first-arrival = shortest — A থেকে BFS চালালে B প্রথমবার যে layer-এ ছোঁয়া হয়, সেটাই সবচেয়ে কম ধাপ।

দ্বিতীয়ত, path reconstruction via parent pointers — discovery-র সময় প্রতিটা cell-এর জন্য store করো "আমাকে কে আর কোন দিক থেকে enqueue করল" (parent[next] = (current, move))। BFS শেষে B থেকে parent ধরে পেছনে হাঁটো A পর্যন্ত, পথে move-অক্ষরগুলো জমাও, তারপর উল্টে দাও — পাওয়া গেল A→B পথ। BFS shortest নিশ্চিত করে বলে এই reconstructed পথও shortest।

4. Which data structure is needed?

  • Grid নিজেই — implicit graph; neighbor চার দিকের non-# cell।
  • collections.deque — BFS frontier; FIFO-ই shortest নিশ্চিত করে।
  • visited চিহ্ন — হয় আলাদা set/2D array, বা parent-এ entry থাকা মানেই visited।
  • parent map — প্রতিটা cell-এর জন্য (আগের cell, সেই move-এর অক্ষর), path reconstruct করতে।

5. Why this data structure fits

Grid-কে graph ধরা fit করে কারণ neighbor চার দিকেই fixed। deque fit করে কারণ shortest path-এর জন্য BFS-এর FIFO অপরিহার্য (DFS একটা পথ দেয়, shortest নয় — classic wrong-tool)। parent map fit করে কারণ পথ reconstruct করতে শুধু "কোথা থেকে এলাম আর কোন move-এ" — সেটা একটা back-pointer chain-এ ধরে রাখলেই গন্তব্য থেকে উৎসে ফিরে যাওয়া যায়।

6. Real-life analogy

গোলকধাঁধায় ঢোকার মুখে একটা সুতোর বল হাতে নাও, কিন্তু এবার তুমি একসাথে অনেক দিকে অনুসন্ধানকারী ছড়িয়ে দিচ্ছ (BFS)। প্রতিটা নতুন মোড়ে পৌঁছে একটা ছোট চিরকুট রেখে যাও: "আমি এখানে এসেছি ওই মোড় থেকে, ডান দিকে বাঁক নিয়ে।" শেষে B-তে পৌঁছালে সেখান থেকে চিরকুটগুলো উল্টো দিকে ধরে ধরে A পর্যন্ত ফিরে আসো — প্রতিটা চিরকুট বলে দেয় কোন দিকে এসেছিলে। দিকগুলো উল্টো করে সাজালেই A→B পথ।

7. Visual explanation

ছোট maze [".A.", "#.#", "..B"] (top-left (0,0)) দিয়ে দেখি:

maze (r,c):          A=(0,1), B=(2,2)
  . A .              (0,0)(0,1)(0,2)
  # . #              দেয়াল (1,0),(1,2)
  . . B              (2,0)(2,1)(2,2)

BFS A থেকে, parent লিখছি:
  (0,1) start
  -> (1,1) [D from (0,1)]
  -> (2,1) [D from (1,1)]
  -> (2,2)=B [R from (2,1)]

B থেকে পেছনে: R <- D <- D, উল্টে দিলে "DDR"  (3 ধাপ)

8. Example input and output

Input : maze = [".A.", "#.#", "..B"]
Output: ("YES", 3, "DDR")     # যেকোনো valid shortest path চলবে

Input : maze = ["A#B"]
Output: ("NO",)               # দেয়ালে আটকা, পৌঁছানো যায় না

Edge case (A আর B পাশাপাশি): maze = ["AB"] -> ("YES", 1, "R")

9. Brute force thinking

প্রথম সরল চিন্তা: A থেকে DFS/backtracking দিয়ে সব সম্ভাব্য পথ ঘুরে B-তে পৌঁছানো প্রতিটা পথ মনে রাখা, তারপর তাদের মধ্যে সবচেয়ে ছোটটা বেছে নেওয়া।

1) A থেকে recurse করো, ভিজিট-করা cell মনে রেখে
2) B-তে পৌঁছালে এই পথের দৈর্ঘ্য ও move-string জমা রাখো
3) সব পথ ঘুরে শেষে সবচেয়ে ছোট পথটা return করো

10. Why brute force is slow

সব পথ enumerate করা grid-এ exponential হতে পারে — একই cell বহু ভিন্ন পথে ছোঁয়া হয়, আর backtracking-এ branch বিস্ফোরণ। তাছাড়া DFS যে প্রথম পথ পায় তা shortest হওয়ার গ্যারান্টি নেই, তাই সব ঘুরতেই হয়। অথচ BFS প্রতিটা cell একবার ছুঁয়ে, first-arrival-এই shortest দিয়ে দেয় — O(n·m)। "সব পথ" দরকার নেই, একটা shortest path-ই যথেষ্ট, আর BFS সেটাই দেয়।

11. Key observation

মূল observation: BFS দূরত্বের সাথে parent-pointer রাখলে shortest path নিজেই বেরিয়ে আসে। আলাদা করে পথ খোঁজার দরকার নেই — discovery-র সময়ের back-pointer chain-টাই গন্তব্য থেকে উৎসে shortest পথ ধরে রাখে; শুধু পেছনে হেঁটে উল্টে দিলেই হলো।

12. Optimized intuition

A খুঁজে তাকে queue-তে আর visited-এ রাখো। BFS চালাও: front pop করো, প্রতিটা চলার-যোগ্য (in-bounds, non-#, unvisited) প্রতিবেশীকে mark করো, parent[neighbor] = (cell, move_char) লেখো, enqueue করো। B ছোঁয়ামাত্র থামো। তারপর B থেকে parent ধরে পেছনে হাঁটো A পর্যন্ত, move-অক্ষর জমাও, list উল্টাও — পথ পেলে। B কখনো না ছুঁলে "NO"। O(n·m)।

13. Thinking tweak

মোচড়: "সব পথ খুঁজে সবচেয়ে ছোটটা বাছব" না ভেবে ভাবো "BFS এমনিতেই প্রথমবারেই shortest-এ পৌঁছায় — শুধু আসার সময় 'কোথা থেকে, কোন দিকে' টুকে রাখলেই পথটা পরে উল্টো করে পড়ে নেওয়া যায়।" path enumeration থেকে নেমে এসো একবারের BFS + back-pointer-এ।

14. Step-by-step dry run

maze = [".A.", "#.#", "..B"], A=(0,1), B=(2,2):

  1. seen = {(0,1)}, queue [(0,1)], parent = {}।
  2. pop (0,1) → প্রতিবেশী: (0,0) [L], (0,2) [R], (1,1) [D] সব valid → mark, parent লেখো, enqueue। ((−1,1) বাইরে।)
  3. pop (0,0) → প্রতিবেশী (1,0)='#' বাদ; বাকি seen/বাইরে।
  4. pop (0,2) → (1,2)='#' বাদ; বাকি seen।
  5. pop (1,1) → (2,1) [D] valid → mark, parent[(2,1)]=((1,1),'D'), enqueue।
  6. pop (2,1) → (2,2)=B [R] valid → mark, parent[(2,2)]=((2,1),'R')। B ছোঁয়া হলো!
  7. reconstruct: (2,2)←R←(2,1)←D←(1,1)←D←(0,1)=A। উল্টে: "DDR", দৈর্ঘ্য 3 → ("YES", 3, "DDR")।

15. Python solution

from collections import deque


def labyrinth(maze):
    R, C = len(maze), len(maze[0])
    grid = [list(row) for row in maze]

    # A আর B খুঁজে নাও
    start = end = None
    for r in range(R):
        for c in range(C):
            if grid[r][c] == "A":
                start = (r, c)
            elif grid[r][c] == "B":
                end = (r, c)

    moves = ((-1, 0, "U"), (1, 0, "D"), (0, -1, "L"), (0, 1, "R"))
    seen = {start}
    parent = {}                          # cell -> (আগের cell, move-অক্ষর)
    q = deque([start])

    while q:
        r, c = q.popleft()
        if (r, c) == end:
            break                        # প্রথমবার B ছোঁয়া = shortest
        for dr, dc, ch in moves:
            nr, nc = r + dr, c + dc
            if (0 <= nr < R and 0 <= nc < C
                    and grid[nr][nc] != "#" and (nr, nc) not in seen):
                seen.add((nr, nc))       # push করার সময় mark করো
                parent[(nr, nc)] = ((r, c), ch)
                q.append((nr, nc))

    if end not in seen:
        return ("NO",)

    # B থেকে parent ধরে পেছনে হেঁটে পথ গড়ো
    path = []
    cur = end
    while cur != start:
        prev, ch = parent[cur]
        path.append(ch)
        cur = prev
    path.reverse()                       # উৎস -> গন্তব্য বরাবর
    return ("YES", len(path), "".join(path))


# ---- tests ----
res1 = labyrinth([".A.", "#.#", "..B"])
assert res1[0] == "YES"
assert res1[1] == 3                       # shortest দৈর্ঘ্য নির্দিষ্ট
assert res1[2] == "DDR"

assert labyrinth(["A#B"]) == ("NO",)

res3 = labyrinth(["AB"])
assert res3 == ("YES", 1, "R")

# একটু বড় maze, একাধিক shortest path সম্ভব -> দৈর্ঘ্য যাচাই করি
res4 = labyrinth(["A..", "...", "..B"])
assert res4[0] == "YES"
assert res4[1] == 4                       # Manhattan দূরত্ব 4
print("সব test pass!")

16. Line-by-line code explanation

  • grid = [list(row) for row in maze] — string সারিগুলোকে index-যোগ্য list বানানো।
  • A/B খোঁজার double loop — start ও end coordinate।
  • moves — চার দিকের (dr, dc, অক্ষর); অক্ষরটাই path-এ যাবে।
  • seen = {start} / parent = {} — start আগেই visited; parent খালি (start-এর কোনো parent নেই)।
  • if (r, c) == end: break — B pop হওয়ামাত্র থামো; BFS বলে এটাই shortest।
  • parent[(nr,nc)] = ((r,c), ch) ঠিক seen.add-এর পাশে — কে enqueue করল ও কোন move-এ।
  • reconstruction loop — B থেকে parent ধরে A পর্যন্ত পেছনে; path.reverse() করে উৎস→গন্তব্য।

17. Output walkthrough

labyrinth([".A.", "#.#", "..B"]): BFS (0,1) থেকে শুরু, (1,1) তারপর (2,1) হয়ে (2,2)=B ছোঁয়; parent chain উল্টে "DDR", দৈর্ঘ্য 3 → ("YES", 3, "DDR")। "A#B"-তে B অপৌঁছনীয় → ("NO",)। "AB" → এক ধাপ ডানে → ("YES", 1, "R")। বড় maze-এ shortest দৈর্ঘ্য 4। সব assert pass, শেষে print: সব test pass!।

18. Time complexity

O(n · m) — BFS-এ প্রতিটা cell একবার pop, প্রতিটা edge constant-বার দেখা; A/B খোঁজা ও reconstruction-ও বড়জোর O(n·m)।

19. Space complexity

O(n · m) — seen, parent, আর queue প্রতিটা worst case O(n·m); reconstructed path বড়জোর O(n·m) লম্বা।

20. Common mistakes

  • shortest path-এর জন্য DFS ব্যবহার করা — DFS একটা পথ দেয়, shortest নয়; এটা classic wrong-tool error। BFS নাও।
  • parent store করতে ভুলে যাওয়া — তখন দূরত্ব পাও কিন্তু পথ reconstruct করা যায় না।
  • শেষে path reverse না করা — তখন গন্তব্য→উৎস উল্টো string পাও।
  • দিক ও অক্ষরের mapping গুলিয়ে ফেলা — dr=-1 মানে up (U), dr=+1 মানে down (D); সারি বাড়া = নিচে নামা।

21. Which basic problem this inherits from

ভিত্তি: BFS shortest-path থিওরেম (../bfs.md) আর queue (../../04-stack-and-queue/)। এটা প্রথম problem এই tracker-এ যেখানে শুধু দূরত্ব নয়, আসল পথ চাই — তাই BFS-এর সাথে parent-pointer যোগ করা শেখায়। মূল নতুন শিক্ষা: discovery-র সময় back-pointer রাখলে পরে যেকোনো shortest-path problem-এ পথ reconstruct করা যায় — একটা পুনর্ব্যবহারযোগ্য কৌশল।

22. Similar harder problems

23. Pattern learned

Grid BFS + path reconstruction: unweighted shortest path-এ BFS first-arrival = shortest; আসল পথ চাইলে discovery-র সময় parent[next] = (cur, move) রাখো, শেষে গন্তব্য থেকে পেছনে হেঁটে উল্টে দাও। DFS এখানে wrong tool। খরচ O(n·m)।

24. Final summary

ভবিষ্যতের আমাকে: "labyrinth = grid BFS + parent pointers; প্রথমবার B ছোঁয়া = shortest, parent chain উল্টে দিলে পথ।" যখনই 'shortest path এবং পথটা কী' দেখবে — BFS চালাও, আসার সময় 'কোথা থেকে, কোন দিকে' টুকে রাখো, গন্তব্য থেকে পেছনে হেঁটে reconstruct করো; DFS দিয়ে shortest খোঁজার ফাঁদে পা দিয়ো না।

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