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:
  1. Right (1): grid[i][j] se grid[i][j + 1] jaana hai.

  2. Left (2): grid[i][j] se grid[i][j - 1] jaana hai.

  3. Down (3): grid[i][j] se grid[i + 1][j] jaana hai.

  4. Up (4): grid[i][j] se grid[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:

  1. m ==

  2. n == grid[i].length

  3. 1≤m,n≤1001 \leq m, n \leq 100

  4. 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.

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.

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];
    }
}

				
			
    1. Initialize Grid Size:

      • Hum pehle m aur n variables initialize karte hain jo grid ke rows aur columns ka size store karte hain.

    2. Initialize minCost Array:

      • Ek 2D array minCost initialize kiya gaya hai jo har cell tak pahunchne ki minimum cost store karega. Initially, is array ko Infinity se fill karte hain taaki sabki cost maximum remains.

    3. 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.

    4. 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].

    5. 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.

    6. Visit Adjacent Cells:

      • Har adjacent cell ke liye, hum new row nr aur new column nc 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.

    7. Update Costs and Priorities:

      • Agar nr aur nc valid bounds mein hain aur new cost, existing cost se kam hai, to minCost[nr][nc] update kiya jata hai.

      • Agar cost 1 hai to nr, nc ko deque ke back mein add karte hain, aur agar cost 0 hai to deque ke front mein add karte hain.

    8. 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<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        // 2D array `minCost` initialize karte hain
        vector<vector<int>> minCost(m, vector<int>(n, INT_MAX));
        
        deque<pair<int, int>> dque;
        dque.push_front({0, 0});
        minCost[0][0] = 0;
        
        vector<vector<int>> 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.