Minimum Cost to Make at Least One Valid Path in a Grid
Problem Statement
Ek m×nm \times n grid diya gaya hai. Is grid ke har cell mein ek sign hai jo dikhata hai agla cell jo aapko visit karna chahiye jab aap us cell mein ho.
Sign Meanings:
Right (1):
grid[i][j]
segrid[i][j + 1]
jaana hai.Left (2):
grid[i][j]
segrid[i][j - 1]
jaana hai.Down (3):
grid[i][j]
segrid[i + 1][j]
jaana hai.Up (4):
grid[i][j]
segrid[i - 1][j]
jaana hai.
Notice karo ki kuch signs grid ke baahar point bhi kar sakte hain.
Objective:
Aapko upper left cell (0, 0) se shuru karna hai. Ek valid path grid mein woh path hota hai jo (0, 0) se start hota hai aur bottom-right cell (m – 1, n – 1) tak reach karta hai, grid ke signs ko follow karte hue. Path shortest hone ki zaroorat nahi hai.
Aap ek cell ka sign modify kar sakte hain cost = 1 par aur har cell ka sign ek hi baar modify kiya ja sakta hai.
Final goal ye hai ki kam se kam ek valid path banane ka minimum cost return karna hai.
Examples:
Example 1:
Input: grid = [[1, 1, 1, 1], [2, 2, 2, 2], [1, 1, 1, 1], [2, 2, 2, 2]]
Output: 3
Explanation:
Start at (0, 0).
The path to (3, 3) with valid directions:
(0, 0) –> (0, 1) –> (0, 2) –> (0, 3) change arrow to down with cost = 1 –> (1, 3) –> (1, 2) –> (1, 1) –> (1, 0) change arrow to down with cost = 1 –> (2, 0) –> (2, 1) –> (2, 2) –> (2, 3) change arrow to down with cost = 1 –> (3, 3)
Total cost = 3.
Example 2:
Input: grid = [[1, 1, 3], [3, 2, 2], [1, 1, 4]]
Output: 0
Explanation:
Without any modifications, follow the path from (0, 0) to (2, 2).
Example 3:
Input: grid = [[1, 2], [4, 3]]
Output: 1
Constraints:
m ==
n == grid[i].length
1≤m,n≤1001 \leq m, n \leq 100
1≤grid[i][j]≤4
Minimum Cost to Make at Least One Valid Path in a Grid
Is problem ko solve karne ke liye hum ek graph traversal algorithm ka use kar sakte hain with a priority queue. Iska matlab hai ki hum sabse kam cost waalon paths ko pehle explore karenge.
Priority Queue Use:
Hum priority queue jaise structures ka use karte hain (e.g., Dijkstra's algorithm) taaki hum lowest cost wale path pehle explore kar sakein.
Queue use karke, hum waale cells ko queue mein dalenge jin path ke directions hum change karte hain aur unki cost 1 add karenge queue mein.
Initial State Se Start Karna:
Start karte hain upper-left cell (0, 0) se. Ek valid path follow karte hue explore karte hain signs use karke.
Queue mein har cell ka direction aur uski cost dalte hain.
Path Traverse Karna:
Har cell ka cost check karte hue, hum new cell explore karte hain. Agar current cell se agla cell default direction follow nahi karta, toh cost 1 add karenge aur us direction ko queue mein daalenge.
Ye ensure karta hai ki hum kam se kam cost pe bottom right cell tak pahunch jayein.
Terminating Condition:
Jab bottom-right cell tak pahunch jate hain, hum minimum cost return karte hain.Intuition
0-1 BFS Algorithm Ka Use:
Hum 0-1 Breadth-First Search (BFS) algorithm use karenge with a deque (double-ended queue).
Initialize 2D Array:
Ek 2D array minCost initialize karenge jo har cell tak pahunchne ki minimum cost store karega.
Start From Top-Left Cell:
Top-left cell (0,0) se shuru karte hain aur neighboring cells explore karte hain.
Matching Direction:
Agar current direction grid ke direction se match karta hai, to us cell ko deque ke front mein add karte hain (no cost).
Non-Matching Direction:
Agar direction match nahi karta, to us cell ko deque ke back mein add karte hain (cost of 1).
Continue Until Bottom-Right Cell:
Ye process tab tak continue karte hain jab tak bottom-right cell tak pahunch nahi jaate ya phir sab cells explore nahi ho jaate.Approach
Time Complexity: O(m * n)
Hum har cell ko ek baar visit karenge aur har direction ko check karenge.
Poore grid ke m * n cells hain, to humara traversal time complexity O(m * n) hota hai.
Matlab, agar grid ka size bada hota hai, to time bhi usi ke according linearly badhega.
Space Complexity: O(m * n)
Hum ek 2D array
minCost
ko maintain karte hain jo har cell tak pahunchne ki minimum cost store karta hai.Is array ki space complexity bhi O(m * n) hoti hai kyunki poora grid size store kiya gaya hai.
Matlab, jitna larger grid size hoga, utni hi zyaada memory occupy hogi.
Solution
class Solution {
minCost(grid) {
const m = grid.length;
const n = grid[0].length;
// 2D array `minCost` initialize karte hain
let minCost = Array.from({ length: m }, () => Array(n).fill(Infinity));
const dque = [];
dque.unshift([0, 0]);
minCost[0][0] = 0;
const directions = [
[0,1], [0,-1], [1,0], [-1,0]
];
while (dque.length) {
const [r, c] = dque.shift();
// Adjacent cells visit karte hain
for (let i = 0; i < 4; i++) {
const [dr, dc] = directions[i];
const nr = r + dr;
const nc = c + dc;
const cost = (grid[r][c] !== (i + 1)) ? 1 : 0;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && minCost[r][c] + cost < minCost[nr][nc]) {
minCost[nr][nc] = minCost[r][c] + cost;
if (cost === 1) {
dque.push([nr, nc]); // Priority back of the deque
} else {
dque.unshift([nr, nc]); // Priority front of the deque
}
}
}
}
return minCost[m - 1][n - 1];
}
}
Initialize Grid Size:
Hum pehle
m
aurn
variables initialize karte hain jo grid ke rows aur columns ka size store karte hain.
Initialize
minCost
Array:Ek 2D array
minCost
initialize kiya gaya hai jo har cell tak pahunchne ki minimum cost store karega. Initially, is array koInfinity
se fill karte hain taaki sabki cost maximum remains.
Use Deque:
Ek double-ended queue (deque) use kiya gaya hai. Start point (0,0) ko deque ke front mein add kiya gaya hai aur
minCost[0][0]
ko 0 set kiya gaya hai kyunki woh humara initial point hai.
Set Directions:
Ek
directions
array define kiya gaya hai jo 4 possible movements specify karta hai: right [0,1], left [0,-1], down [1,0], aur up [-1,0].
Traverse Deque:
Jab tak deque mein elements hain, hum traverse karte hain.
Har iteration mein (r, c) ko deque ke front se nikalte hain aur use current cell consider karte hain.
Visit Adjacent Cells:
Har adjacent cell ke liye, hum new row
nr
aur new columnnc
calculate karte hain current direction ke hisaab se.Fir,
cost
calculate karte hain jaise agar current direction match karta hai to cost 0 hai, nahi to 1.
Update Costs and Priorities:
Agar
nr
aurnc
valid bounds mein hain aur new cost, existing cost se kam hai, tominCost[nr][nc]
update kiya jata hai.Agar
cost
1 hai tonr, nc
ko deque ke back mein add karte hain, aur agarcost
0 hai to deque ke front mein add karte hain.
Return Result:
Jab sab cells explore ho jate hain, to minimum cost return ki jati hai jo bottom-right cell
minCost[m-1][n-1]
tak pahunchne ke liye chahiye.
Solution
class Solution {
public:
int minCost(vector>& grid) {
int m = grid.size();
int n = grid[0].size();
// 2D array `minCost` initialize karte hain
vector> minCost(m, vector(n, INT_MAX));
deque> dque;
dque.push_front({0, 0});
minCost[0][0] = 0;
vector> directions = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
while (!dque.empty()) {
auto [r, c] = dque.front();
dque.pop_front();
// Adjacent cells visit karte hain
for (int i = 0; i < 4; ++i) {
int nr = r + directions[i][0];
int nc = c + directions[i][1];
int cost = (grid[r][c] != (i + 1)) ? 1 : 0;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && minCost[r][c] + cost < minCost[nr][nc]) {
minCost[nr][nc] = minCost[r][c] + cost;
if (cost == 1) {
dque.push_back({nr, nc}); // Priority back of the deque
} else {
dque.push_front({nr, nc}); // Priority front of the deque
}
}
}
}
return minCost[m - 1][n - 1];
}
};
Initialize
minCost
Array: Hum ek 2D array initialize karte hain jo har cell tak pohonchne ka minimum cost store karega.Use Deque: Deque use karke, hum front se cells fetch karte hain aur cost ke hisaab se back ya front mein add karenge.
Set Directions: 4 possible movements specify kiya gaye hain: right, left, down, aur up.
Traverse Deque: Jab tak deque empty nahi hoti, hum cells ko traverse karte hain.
Visit Adjacent Cells: Har direction ke cells ko check karte hain aur cost calculate karte hain.
Update Costs and Priorities: Cost ke hisaab se, cells ko deque ke back ya front mein add karte hain.
Return Result: Minimum cost return karte hain jo bottom-right cell tak pahunchne ke liye chahiye.