Problem link ও উৎস
- **Original source:** Grid-এ minimax shortest-path-এর classic প্রয়োগ
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Hard
- **Pattern:** minimax Dijkstra (path বরাবর সর্বোচ্চ elevation minimize)
- **Basic idea inherited from:** minimax Dijkstra (এই tracker-এর #20); পরে আবার করো [../../10-disjoint-set-union/](../../10-disjoint-set-union/README.md) দিয়ে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে `n × n` একটা grid দেওয়া আছে; প্রতিটা cell-এ একটা সংখ্যা — সেই জায়গার উচ্চতা (elevation)। সময় `t`-তে জলের স্তর `t`। তুমি কোনো cell-এ থাকতে বা সেখানে সাঁতরে যেতে পারো শুধু তখনই, যখন জলের স্তর সেই cell-এর elevation-এর সমান বা বেশি — অর্থাৎ সেই cell ডুবে গেছে। তুমি বাঁ-উপরের cell `(0,0)` থেকে শুরু করে ডান-নিচের cell `(n-1,n-1)`-এ পৌঁছাতে চাও (চার পাশে চলা যায়)। সবচেয়ে কম কোন সময়ে পৌঁছানো সম্ভব, সেটা বের করো।
```text
grid:
0 2
1 3
t=3-এ পথ 0 -> 1 -> 3 (অথবা 0 -> 2 -> 3): এই path-এ সর্বোচ্চ elevation 3
আগে (t<3) destination 3 ডোবেই না।
উত্তর: 3
```
### Input ও output {#8-example-input-and-output}
```text
Input : grid = [[0,2],[1,3]]
Output: 3
Input : grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Edge case (একটাই cell): grid = [[0]] -> 0
Edge case (start-ই উঁচু): grid = [[3,2],[0,1]] -> 3 (start 3, পুরো path-এর max অন্তত 3)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা নিচু জমিতে বৃষ্টিতে আস্তে আস্তে জল জমছে। তুমি এক কোণ থেকে আরেক কোণে সাঁতরে যেতে চাও, কিন্তু কোনো জায়গা পার হতে পারবে কেবল যখন সেটা জলে ডুবেছে। উঁচু ঢিবিগুলো সবচেয়ে দেরিতে ডোবে। তোমার যাত্রার সবচেয়ে উঁচু ঢিবিটাই ঠিক করে দেয় কখন তুমি পুরো পথ পেরোতে পারবে। তাই তুমি এমন পথ খোঁজো যার সবচেয়ে উঁচু ঢিবিটা যতটা সম্ভব নিচু — সেটাই সবচেয়ে কম অপেক্ষা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **minimax Dijkstra**-র উপর দাঁড়িয়ে (#20, Path With Minimum Effort)। #20-এ path-এর cost ছিল পাশাপাশি cell-এর height-পার্থক্যের সর্বোচ্চ; এখানে cost হলো path বরাবর cell-গুলোর **elevation-এর সর্বোচ্চ**। কারণ কোনো path ধরে যেতে গেলে অপেক্ষা করতে হবে যতক্ষণ না সেই path-এর সবচেয়ে উঁচু cell-টাও ডোবে — তাই সময় = path-এর max elevation, আর আমরা সেই max-কে minimize করতে চাই। [../shortest-path.md](../shortest-path.md)-এর শেষ trigger: "minimum possible maximum along a path (minimax)।"
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: "সময়" আর "path-এর max elevation" আসলে এক জিনিস। সময় `t`-তে কেবল সেইসব cell ব্যবহারযোগ্য যাদের elevation ≤ t। তাই `(0,0)` থেকে `(n-1,n-1)`-এ যাওয়ার ন্যূনতম সময় = সেই path-এর max elevation যেটার max-elevation সবচেয়ে ছোট। এটাই minimax shortest path। আর invariant যেটা Dijkstra-কে বৈধ রাখে: path বাড়ালে তার max elevation কখনো কমে না (`max` একমুখী) — তাই "cheapest known first, একবার final হলে আর বদলায় না" greedy নিরাপদ ([../shortest-path.md](../shortest-path.md)-এর safety proof)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **min-heap** (`heapq`), grid-এর implicit adjacency (চার দিকের neighbor), আর একটা 2D **visited** array — কোনো cell-এর final (সবচেয়ে ছোট max-elevation) একবার বের হয়ে গেলে আবার process না করতে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Min-heap fit করে কারণ প্রতি ধাপে দরকার "সব frontier cell-এর মধ্যে সবচেয়ে ছোট path-max-elevation-ওয়ালা cell"; heap সেটা O(log n)-এ দেয়। যেহেতু `max`-based cost কখনো কমে না, Dijkstra-র greedy frontier সঠিক — তাই Bellman-Ford-এর ধীর pass লাগে না, heap-ই যথেষ্ট। visited array fit করে কারণ একবার কোনো cell সবচেয়ে কম সময়ে পৌঁছানো প্রমাণ হলে তাকে আবার expand করা শুধু অপচয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: উত্তরের উপর binary search। একটা সময় `t` ধরো; শুধু `elevation ≤ t` cell ব্যবহার করে `(0,0)` থেকে `(n-1,n-1)`-এ DFS/BFS-এ পৌঁছানো যায় কিনা দেখো। যায় হলে `t` ছোট করার চেষ্টা করো, না গেলে বড় করো — সবচেয়ে ছোট সম্ভব `t`-ই উত্তর।
```text
1) lo=grid[0][0], hi=max elevation
2) mid = (lo+hi)//2; elevation<=mid cell দিয়ে reachable?
3) reachable -> hi=mid ; নাহলে lo=mid+1
4) lo == উত্তর
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
binary-search-plus-flood approach ভুল নয় (`O(n^2 log(maxElev))`) — কিন্তু প্রতিটা candidate `t`-এর জন্য পুরো grid নতুন করে flood করতে হয়, একই কাজ বারবার। Dijkstra সেটা এক পাসেই করে: প্রতিটা cell-এর "সবচেয়ে ছোট path-max" সরাসরি বের করে, বারবার reachability পরীক্ষা ছাড়াই। মূল অপচয়: একই grid-কে বহু `t`-এর জন্য আবার আবার explore করা, যেখানে minimax Dijkstra তথ্যটা একবারেই জমিয়ে ফেলে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: সময় `t`-তে পৌঁছানোর শর্ত = এমন path থাকা যার সব cell-এর elevation ≤ t, অর্থাৎ যার max elevation ≤ t। তাই ন্যূনতম সময় = সব path-এর মধ্যে সবচেয়ে ছোট "max elevation"। এটা ঠিক minimax shortest path — Dijkstra দিয়ে relax-এ `max` বসিয়ে সরাসরি বের হয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Dijkstra চালাও, কিন্তু path-cost = path বরাবর সর্বোচ্চ elevation। heap-এ `(এ পর্যন্ত max elevation, r, c)` রাখো, শুরুতে `(grid[0][0], 0, 0)`। সবচেয়ে ছোট max-elevation-ওয়ালা cell pop করো; neighbor-এ গেলে নতুন cost = `max(এ পর্যন্ত, neighbor-এর elevation)`। destination প্রথমবার pop হলেই সেটাই উত্তর — কারণ ওই মুহূর্তে তার path-max প্রমাণিতভাবে সবচেয়ে ছোট (frontier-এর বাকিরা ≥, আর extension শুধু সমান/বড় করে)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সময়" শব্দটা যেন বিভ্রান্ত না করে — সময় `t`-তে যাওয়া যায় মানে path-এর সব cell ≤ t, মানে path-এর max ≤ t। তাই "ন্যূনতম সময়" = "সবচেয়ে ছোট path-max-elevation" = minimax Dijkstra। #20-এর সাথে একমাত্র পার্থক্য: cost-এ step-পার্থক্যের বদলে cell-এর নিজের elevation।
### ছবিতে বোঝা {#7-visual-explanation}
`grid = [[0,2],[1,3]]`, heap-এ `(এ পর্যন্ত path-এর max elevation, r, c)`:
```text
start (0,0) elevation 0
pop (0, 0,0): neighbors
(0,1) elev 2 -> push (max(0,2)=2, 0,1)
(1,0) elev 1 -> push (max(0,1)=1, 1,0)
heap: (1,1,0) (2,0,1)
pop (1, 1,0) elevation 1:
(1,1) elev 3 -> push (max(1,3)=3, 1,1)
heap: (2,0,1) (3,1,1)
pop (2, 0,1) elevation 2:
(1,1) elev 3 -> push (max(2,3)=3, 1,1)
heap: (3,1,1) (3,1,1)
pop (3, 1,1): destination! return 3
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`grid = [[0,2],[1,3]]` (উত্তর 3):
1. `visited` সব False। heap `[(0, 0, 0)]` (start elevation 0)।
2. pop `(0, 0,0)`। destination নয়, mark visited। neighbor `(0,1)` elev 2 → push `(2,0,1)`; `(1,0)` elev 1 → push `(1,1,0)`। heap `[(1,1,0),(2,0,1)]`।
3. pop `(1, 1,0)`। mark visited। neighbor `(1,1)` elev 3 → push `(max(1,3)=3, 1,1)`। heap `[(2,0,1),(3,1,1)]`।
4. pop `(2, 0,1)`। mark visited। neighbor `(1,1)` elev 3 → push `(3,1,1)`। heap `[(3,1,1),(3,1,1)]`।
5. pop `(3, 1,1)` — এটাই destination `(1,1)` → return `3`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
def swim_in_water(grid):
# minimax Dijkstra: time = path বরাবর cell-গুলোর সর্বোচ্চ elevation
n = len(grid)
visited = [[False] * n for _ in range(n)]
heap = [(grid[0][0], 0, 0)] # (এ পর্যন্ত path-এর max elevation, r, c)
while heap:
t, r, c = heapq.heappop(heap)
if (r, c) == (n - 1, n - 1):
return t # destination first pop = answer
if visited[r][c]:
continue
visited[r][c] = True
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
# নতুন path-cost = পুরোনো max আর নতুন cell-এর max
heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
return -1
# ---- tests ----
assert swim_in_water([[0, 2], [1, 3]]) == 3
assert swim_in_water([[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]]) == 16
assert swim_in_water([[0]]) == 0
assert swim_in_water([[3, 2], [0, 1]]) == 3
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `visited = [[False]*n ...]` — প্রতিটা cell-এর final বের হয়ে গেছে কিনা; একবার pop করে process হলে True।
- `heap = [(grid[0][0], 0, 0)]` — start cell, এ পর্যন্ত path-max = তার নিজের elevation; cost আগে রাখা জরুরি।
- `if (r, c) == (n-1, n-1): return t` — destination প্রথমবার pop হলেই path-max final, return।
- `if visited[r][c]: continue` — lazy deletion: stale heap entry বাদ ([../shortest-path.md](../shortest-path.md)-এর trick)।
- `visited[r][c] = True` — এই cell-এর সবচেয়ে ছোট path-max এখন প্রমাণিত।
- `max(t, grid[nr][nc])` — মূল মোচড়: নতুন path-cost = এ পর্যন্ত max আর neighbor-এর elevation-এর বড়টা।
- `heapq.heappush(...)` — neighbor-কে নতুন cost সহ frontier-এ ঢোকাও (lazy: পুরোনো entry আলাদা করে মুছি না)।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`swim_in_water([[0,2],[1,3]])`: heap সবচেয়ে ছোট path-max আগে ছাড়ে। `(0,0)` থেকে `(1,0)` (1) আর `(0,1)` (2) frontier-এ আসে; দুটো পথেই destination `(1,1)`-এ পৌঁছাতে হলে elevation 3 cell পেরোতে হয়, তাই destination 3 নিয়ে pop হয় → return 3। বড় grid-এ সর্পিল পথ ধরে সবচেয়ে ছোট max হয় 16 → return 16। বাকি assert pass, শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n^2 · log n)** — grid-এ `n^2` টা cell, প্রতিটা heap-এ কয়েকবার push হতে পারে, প্রতিটা heap operation `log(n^2) = O(log n)`। edge সংখ্যা `O(n^2)` (প্রতি cell 4 neighbor) ধরে standard Dijkstra খরচ।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n^2)** — `visited` array আর heap, দুটোতেই সর্বোচ্চ `O(n^2)` entry জমতে পারে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- relax-এ `max(t, elevation)`-এর বদলে `t + elevation` বা step-পার্থক্য লেখা — এটা #20 নয়, এখানে cost cell-এর নিজের elevation-এর max।
- `(cost, r, c)`-এর বদলে `(r, c, cost)` push করা — heap তখন row দিয়ে sort করে, ভুল।
- start cell-এর cost 0 ধরা, `grid[0][0]` না নেওয়া — start উঁচু হলে (`[[3,2],[0,1]]`) উত্তর কম আসবে।
- destination pop-এ return না করে পুরো heap চালানো — সঠিক হলেও অপ্রয়োজনীয়; first pop = final।
- `if visited[r][c]: continue` বাদ দেওয়া — correctness টিকলেও stale entry re-expand হয়ে ধীর।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: **minimax Dijkstra** (#20, Path With Minimum Effort; [../shortest-path.md](../shortest-path.md))। আটকে গেলে আগে #20-এর কাঠামো মনে করো — heap-এ `(cost, r, c)`, relax-এ `max`, destination first pop। এখানে শুধু cost-এর সংজ্ঞা আলাদা: step-পার্থক্যের বদলে cell-এর নিজের elevation। বাকি সব এক।
### পরের অনুশীলন {#22-similar-harder-problems}
- Path With Minimum Effort (একই minimax Dijkstra, cost = step-পার্থক্য) —