# Minimum Cost to Make at Least One Valid Path in a Grid
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Array, Heap (Priority Queue), Matrix, Graph
**Companies:** [Cleartrip](https://scaleengineer.com/companies/cleartrip)
---
## Problem
Given an `m x n` grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of `grid[i][j]` can be:

* `1` which means go to the cell to the right. (i.e go from `grid[i][j]` to `grid[i][j + 1]`)
* `2` which means go to the cell to the left. (i.e go from `grid[i][j]` to `grid[i][j - 1]`)
* `3` which means go to the lower cell. (i.e go from `grid[i][j]` to `grid[i + 1][j]`)
* `4` which means go to the upper cell. (i.e go from `grid[i][j]` to `grid[i - 1][j]`)

Notice that there could be some signs on the cells of the grid that point outside the grid.

You will initially start at the upper left cell `(0, 0)`. A valid path in the grid is a path that starts from the upper left cell `(0, 0)` and ends at the bottom-right cell `(m - 1, n - 1)` following the signs on the grid. The valid path does not have to be the shortest.

You can modify the sign on a cell with `cost = 1`. You can modify the sign on a cell **one time only**.

Return _the minimum cost to make the grid have at least one valid path_.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/image0.png) 

**Input:** grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
**Output:** 3
**Explanation:** You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3)
The total cost = 3.

**Example 2:**

![](https://assets.glich.co/dsa/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/image1.png) 

**Input:** grid = [[1,1,3],[3,2,2],[1,1,4]]
**Output:** 0
**Explanation:** You can follow the path from (0, 0) to (2, 2).

**Example 3:**

![](https://assets.glich.co/dsa/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/image2.png) 

**Input:** grid = [[1,2],[4,3]]
**Output:** 1

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 100`
* `1 <= grid[i][j] <= 4`

# Approaches
## Bellman-Ford Algorithm
This problem can be modeled as finding the shortest path in a weighted graph. The grid cells are the vertices, and possible moves between adjacent cells are the edges. A move that follows the grid's sign has a weight of 0, while a move that requires changing the sign has a weight of 1. The Bellman-Ford algorithm is a classic algorithm for finding the shortest paths from a single source vertex to all other vertices in a weighted digraph. While it's more general than needed here (it can handle negative edge weights), it provides a straightforward, albeit inefficient, solution.
**Time:** `O((m*n)^2)`. The outer loop runs `m*n` times, and the inner loops iterate through all `m*n` cells and their 4 neighbors. · **Space:** `O(m*n)` to store the `dist` array.
**Pros:** Relatively simple to understand and implement.; Correctly solves the problem.
**Cons:** Very inefficient due to its high time complexity. It re-evaluates all `m*n` cells in each of the `m*n` iterations.
### Explanation
We create a 2D array `dist[m][n]` to store the minimum cost to reach each cell `(i, j)` from the start `(0, 0)`. Initialize all costs to infinity, except for `dist[0][0]`, which is 0.
The algorithm works by repeatedly relaxing edges. We iterate `m * n` times (the total number of vertices). In each iteration, we traverse all cells `(r, c)` in the grid.
For each cell `(r, c)`, we consider moving to its four neighbors `(nr, nc)`.
The cost of an edge from `(r, c)` to `(nr, nc)` is 0 if the move aligns with the sign at `grid[r][c]`, and 1 otherwise.
We "relax" the edge by updating the cost to the neighbor: `dist[nr][nc] = min(dist[nr][nc], dist[r][c] + edge_cost)`.
After `m * n - 1` iterations, `dist[m-1][n-1]` will hold the minimum cost to reach the destination. The extra iteration is to ensure convergence for the longest possible simple path.
The final answer is `dist[m-1][n-1]`.
```java
class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            java.util.Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        dist[0][0] = 0;

        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // R, L, D, U -> map to 1, 2, 3, 4

        boolean changed = true;
        // We can optimize by stopping if no distances change in an iteration.
        // A simple path has at most m*n-1 edges.
        for (int i = 0; i < m * n && changed; i++) {
            changed = false;
            for (int r = 0; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    if (dist[r][c] == Integer.MAX_VALUE) {
                        continue;
                    }
                    for (int j = 0; j < 4; j++) {
                        int nr = r + dirs[j][0];
                        int nc = c + dirs[j][1];
                        
                        if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                            int cost = (grid[r][c] == j + 1) ? 0 : 1;
                            if (dist[r][c] + cost < dist[nr][nc]) {
                                dist[nr][nc] = dist[r][c] + cost;
                                changed = true;
                            }
                        }
                    }
                }
            }
        }

        return dist[m - 1][n - 1];
    }
}
```
### Algorithm
*   Initialize a `dist` array of size `m x n` with infinity, and set `dist[0][0] = 0`.
*   Repeat `m * n` times:
    *   For each cell `(r, c)` from `(0, 0)` to `(m-1, n-1)`:
        *   For each of the four possible directions `d` (1 to 4):
            *   Calculate the neighbor cell `(nr, nc)`.
            *   If `(nr, nc)` is within the grid boundaries:
                *   Determine the `edge_cost`: 0 if `d` matches `grid[r][c]`, 1 otherwise.
                *   Update the cost to the neighbor: `dist[nr][nc] = min(dist[nr][nc], dist[r][c] + edge_cost)`.
*   Return `dist[m-1][n-1]`.

## Dijkstra's Algorithm with a Priority Queue
This approach treats the grid as a graph and applies Dijkstra's algorithm to find the shortest path from `(0, 0)` to `(m-1, n-1)`. Dijkstra's algorithm is well-suited for finding the shortest paths in a graph with non-negative edge weights. It works by maintaining a set of visited vertices and iteratively selecting the unvisited vertex with the smallest known distance from the source.
**Time:** `O(m*n * log(m*n))`. There are `m*n` vertices and at most `4*m*n` edges. Each push and pop operation on the priority queue takes `O(log(m*n))` time. · **Space:** `O(m*n)` for the `dist` array and the priority queue, which can store up to all `m*n` cells in the worst case.
**Pros:** Significantly more efficient than the Bellman-Ford approach.; A standard and well-known algorithm for shortest path problems.
**Cons:** The `log(V)` factor from the priority queue operations makes it slightly less efficient than specialized algorithms for graphs with only 0/1 edge weights.
### Explanation
We use a priority queue to store tuples of `(cost, row, col)`, ordered by `cost`. This ensures that we always explore the path with the minimum current cost.
A `dist[m][n]` array is used to keep track of the minimum cost to reach each cell. It's initialized with infinity, and `dist[0][0]` is set to 0.
We start by adding `(0, 0, 0)` to the priority queue.
While the priority queue is not empty, we extract the element `(cost, r, c)` with the smallest cost.
If this cost is greater than the already known minimum cost to reach `(r, c)` (i.e., `cost > dist[r][c]`), we skip it, as we've found a better path already.
If we reach the destination `(m-1, n-1)`, we return the current cost.
For the current cell `(r, c)`, we explore its four neighbors `(nr, nc)`.
For each neighbor, we calculate the cost of the move. The cost is 0 if the move follows the direction specified in `grid[r][c]`, and 1 otherwise.
The new cost to reach the neighbor is `cost + edge_cost`.
If this new cost is less than `dist[nr][nc]`, we update `dist[nr][nc]` and add `(new_cost, nr, nc)` to the priority queue.
```java
class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            java.util.Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        
        // PriorityQueue stores {cost, row, col}
        java.util.PriorityQueue<int[]> pq = new java.util.PriorityQueue<>((a, b) -> a[0] - b[0]);
        
        dist[0][0] = 0;
        pq.offer(new int[]{0, 0, 0});
        
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // R, L, D, U

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int cost = curr[0];
            int r = curr[1];
            int c = curr[2];

            if (cost > dist[r][c]) {
                continue;
            }
            
            if (r == m - 1 && c == n - 1) {
                return cost;
            }

            for (int i = 0; i < 4; i++) {
                int nr = r + dirs[i][0];
                int nc = c + dirs[i][1];
                
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int edgeCost = (grid[r][c] == i + 1) ? 0 : 1;
                    int newCost = cost + edgeCost;
                    
                    if (newCost < dist[nr][nc]) {
                        dist[nr][nc] = newCost;
                        pq.offer(new int[]{newCost, nr, nc});
                    }
                }
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
*   Initialize `dist[m][n]` with infinity, `dist[0][0] = 0`.
*   Create a priority queue `pq` and add `(cost=0, row=0, col=0)`.
*   While `pq` is not empty:
    *   Extract the cell `(cost, r, c)` with the minimum cost from `pq`.
    *   If `cost > dist[r][c]`, continue.
    *   If `(r, c)` is the destination, return `cost`.
    *   For each neighbor `(nr, nc)` of `(r, c)`:
        *   Calculate `edge_cost` (0 or 1).
        *   If `cost + edge_cost < dist[nr][nc]`:
            *   Update `dist[nr][nc] = cost + edge_cost`.
            *   Add `(dist[nr][nc], nr, nc)` to `pq`.

## 0-1 Breadth-First Search (BFS) with a Deque
This is the most efficient approach for this problem. Since the edge weights are restricted to only 0 and 1, we can optimize Dijkstra's algorithm by replacing the priority queue with a double-ended queue (deque). This specialized version of BFS, often called 0-1 BFS, processes nodes in increasing order of cost without the logarithmic overhead of a priority queue.
**Time:** `O(m*n)`. Each cell is added to and removed from the deque exactly once. All operations (add/remove from front/back, neighbor checks) are `O(1)`. · **Space:** `O(m*n)` for the `dist` array and the deque, which can store up to all `m*n` cells.
**Pros:** Optimal time complexity for this problem.; Avoids the logarithmic factor of a priority queue, making it faster than standard Dijkstra's.
**Cons:** Slightly more complex to reason about than standard Dijkstra's if unfamiliar with the 0-1 BFS pattern.
### Explanation
The core idea is to maintain the elements in the deque such that they are sorted by cost. We can achieve this because new paths are either of the same cost (from a 0-cost edge) or cost + 1 (from a 1-cost edge).
We use a `dist[m][n]` array, initialized to infinity, with `dist[0][0] = 0`.
We use a deque and add the starting cell `(0, 0)` to it.
While the deque is not empty, we remove a cell `(r, c)` from the front.
For each of its four neighbors `(nr, nc)`:
Calculate the `edge_cost`. It's 0 if the move follows the sign `grid[r][c]`, and 1 otherwise.
Calculate the `new_cost = dist[r][c] + edge_cost`.
If `new_cost` is less than the current `dist[nr][nc]`:
Update `dist[nr][nc] = new_cost`.
If the `edge_cost` was 0, we add the neighbor `(nr, nc)` to the **front** of the deque. This is because we want to explore these 0-cost paths immediately, as they don't increase the total cost.
If the `edge_cost` was 1, we add the neighbor `(nr, nc)` to the **back** of the deque. These paths have a higher cost and should be explored after all current lower-cost paths.
This process ensures that we always explore cells in non-decreasing order of their costs from the source. The final answer is `dist[m-1][n-1]`.
```java
class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            java.util.Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        
        // Deque stores {row, col}
        java.util.Deque<int[]> deque = new java.util.ArrayDeque<>();
        
        dist[0][0] = 0;
        deque.offerFirst(new int[]{0, 0});
        
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // R, L, D, U

        while (!deque.isEmpty()) {
            int[] curr = deque.pollFirst();
            int r = curr[0];
            int c = curr[1];
            int cost = dist[r][c];

            if (r == m - 1 && c == n - 1) {
                return cost;
            }

            for (int i = 0; i < 4; i++) {
                int nr = r + dirs[i][0];
                int nc = c + dirs[i][1];
                
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int edgeCost = (grid[r][c] == i + 1) ? 0 : 1;
                    int newCost = cost + edgeCost;
                    
                    if (newCost < dist[nr][nc]) {
                        dist[nr][nc] = newCost;
                        if (edgeCost == 0) {
                            deque.offerFirst(new int[]{nr, nc});
                        } else {
                            deque.offerLast(new int[]{nr, nc});
                        }
                    }
                }
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
*   Initialize `dist[m][n]` with infinity, `dist[0][0] = 0`.
*   Create a deque and add `(0, 0)` to the front.
*   While the deque is not empty:
    *   Remove cell `(r, c)` from the front of the deque.
    *   For each neighbor `(nr, nc)` of `(r, c)`:
        *   Calculate `edge_cost` (0 or 1).
        *   If `dist[r][c] + edge_cost < dist[nr][nc]`:
            *   Update `dist[nr][nc] = dist[r][c] + edge_cost`.
            *   If `edge_cost` is 0, add `(nr, nc)` to the front of the deque.
            *   If `edge_cost` is 1, add `(nr, nc)` to the back of the deque.
*   Return `dist[m-1][n-1]`.

# Solutions
### Java

```java
class Solution { public int minCost ( int [][] grid ) { int m = grid . length , n = grid [ 0 ]. length ; boolean [][] vis = new boolean [ m ][ n ]; Deque < int []> q = new ArrayDeque <>(); q . offer ( new int [] { 0 , 0 , 0 }); int [][] dirs = { { 0 , 0 }, { 0 , 1 }, { 0 , - 1 }, { 1 , 0 }, {- 1 , 0 } }; while (! q . isEmpty ()) { int [] p = q . poll (); int i = p [ 0 ], j = p [ 1 ], d = p [ 2 ]; if ( i == m - 1 && j == n - 1 ) { return d ; } if ( vis [ i ][ j ]) { continue ; } vis [ i ][ j ] = true ; for ( int k = 1 ; k <= 4 ; ++ k ) { int x = i + dirs [ k ][ 0 ], y = j + dirs [ k ][ 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n ) { if ( grid [ i ][ j ] == k ) { q . offerFirst ( new int [] { x , y , d }); } else { q . offer ( new int [] { x , y , d + 1 }); } } } } return - 1 ; } }
```

### CPP

```cpp
class Solution { public: int minCost ( vector < vector < int >>& grid ) { int m = grid . size (), n = grid [ 0 ]. size (); vector < vector < bool >> vis ( m , vector < bool > ( n )); vector < vector < int >> dirs = { { 0 , 0 }, { 0 , 1 }, { 0 , - 1 }, { 1 , 0 }, { - 1 , 0 } }; deque < pair < int , int >> q ; q . push_back ({ 0 , 0 }); while ( ! q . empty ()) { auto p = q . front (); q . pop_front (); int i = p . first / n , j = p . first % n , d = p . second ; if ( i == m - 1 && j == n - 1 ) return d ; if ( vis [ i ][ j ]) continue ; vis [ i ][ j ] = true ; for ( int k = 1 ; k <= 4 ; ++ k ) { int x = i + dirs [ k ][ 0 ], y = j + dirs [ k ][ 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n ) { if ( grid [ i ][ j ] == k ) q . push_front ({ x * n + y , d }); else q . push_back ({ x * n + y , d + 1 }); } } } return - 1 ; } };
```

### Python

```python
class Solution : def minCost ( self , grid : List [ List [ int ]]) -> int : m , n = len ( grid ), len ( grid [ 0 ]) dirs = [[ 0 , 0 ], [ 0 , 1 ], [ 0 , - 1 ], [ 1 , 0 ], [ - 1 , 0 ]] q = deque ([( 0 , 0 , 0 )]) vis = set () while q : i , j , d = q . popleft () if ( i , j ) in vis : continue vis . add (( i , j )) if i == m - 1 and j == n - 1 : return d for k in range ( 1 , 5 ): x , y = i + dirs [ k ][ 0 ], j + dirs [ k ][ 1 ] if 0 <= x < m and 0 <= y < n : if grid [ i ][ j ] == k : q . appendleft (( x , y , d )) else : q . append (( x , y , d + 1 )) return - 1
```