Problem link ও উৎস
- **Original source:** CSES Problem Set — Graph Algorithms
- **Platform:** CSES —
- **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](../bfs.md)); queue ([../../04-stack-and-queue/](../../04-stack-and-queue/README.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা গোলকধাঁধা (maze) দেওয়া আছে `n x m` grid হিসেবে: `#` দেয়াল, `.` খালি পথ, `A` শুরুর জায়গা, `B` গন্তব্য। তুমি চার দিকে (উপর-নিচ-বাম-ডান) এক ধাপ করে হাঁটতে পারো, দেয়াল ভেদ করা যায় না। বলো: `A` থেকে `B`-তে পৌঁছানো সম্ভব কিনা; সম্ভব হলে সবচেয়ে কম কত ধাপ লাগে, আর সেই পথটা `U/D/L/R` (up/down/left/right) অক্ষরের একটা string হিসেবে ফেরত দাও।
```text
maze:
# # # # #
# A . . #
# # . # #
# . B . # <- A থেকে B-তে সবচেয়ে ছোট পথ আছে
# # # # #
```
### Input ও output {#8-example-input-and-output}
```text
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")
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
গোলকধাঁধায় ঢোকার মুখে একটা সুতোর বল হাতে নাও, কিন্তু এবার তুমি একসাথে অনেক দিকে অনুসন্ধানকারী ছড়িয়ে দিচ্ছ (BFS)। প্রতিটা নতুন মোড়ে পৌঁছে একটা ছোট চিরকুট রেখে যাও: "আমি এখানে এসেছি ওই মোড় থেকে, ডান দিকে বাঁক নিয়ে।" শেষে `B`-তে পৌঁছালে সেখান থেকে চিরকুটগুলো উল্টো দিকে ধরে ধরে `A` পর্যন্ত ফিরে আসো — প্রতিটা চিরকুট বলে দেয় কোন দিকে এসেছিলে। দিকগুলো উল্টো করে সাজালেই `A→B` পথ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **BFS দিয়ে shortest path** ([../bfs.md](../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-এ ধরে রাখলেই গন্তব্য থেকে উৎসে ফিরে যাওয়া যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: `A` থেকে DFS/backtracking দিয়ে সব সম্ভাব্য পথ ঘুরে `B`-তে পৌঁছানো প্রতিটা পথ মনে রাখা, তারপর তাদের মধ্যে সবচেয়ে ছোটটা বেছে নেওয়া।
```text
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-এ।
### ছবিতে বোঝা {#7-visual-explanation}
ছোট maze `[".A.", "#.#", "..B"]` (top-left (0,0)) দিয়ে দেখি:
```text
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 ধাপ)
```
### ছোট input-এ ধাপে ধাপে {#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")`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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()` করে উৎস→গন্তব্য।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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`); সারি বাড়া = নিচে নামা।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: BFS shortest-path থিওরেম ([../bfs.md](../bfs.md)) আর queue ([../../04-stack-and-queue/](../../04-stack-and-queue/README.md))। এটা প্রথম problem এই tracker-এ যেখানে শুধু দূরত্ব নয়, আসল **পথ** চাই — তাই BFS-এর সাথে parent-pointer যোগ করা শেখায়। মূল নতুন শিক্ষা: discovery-র সময় back-pointer রাখলে পরে যেকোনো shortest-path problem-এ পথ reconstruct করা যায় — একটা পুনর্ব্যবহারযোগ্য কৌশল।
### পরের অনুশীলন {#22-similar-harder-problems}
- Shortest Path in Binary Matrix (grid BFS, দূরত্ব) —