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:
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:
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:
Input: grid = [[1,2],[4,3]] Output: 1
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 1001 <= grid[i][j] <= 4This approach involves using a priority queue to keep track of the cells to explore, always picking the cell from the queue that has the lowest cost accumulated so far. The grid is effectively treated as a graph where each cell represents a node, and moving from one cell to an adjacent one (in the direction indicated by the cell) is a free edge with cost 0, whereas changing direction is an edge with cost 1.
The solution uses BFS with a double-ended queue (deque) to explore the grid. The key idea is to prioritize cells that can be reached with the smallest cost. Here, we use the deque to achieve '0-cost moves' immediately with appendleft, and '1-cost moves' at a later stage with append.
C++
Time complexity is O(m*n), where m and n are the dimensions of the grid, due to each cell being processed in constant time with respect to its neighbors. Space complexity is also O(m*n) due to the storage required for maintaining the costs of each cell.
This approach employs a relaxation technique similar to the Bellman-Ford algorithm. We repeatedly relax the cost to reach each cell to find the shortest path from (0, 0) to (m-1, n-1). This is a valid approach due to the finite grid size and known possible transitions.
This solution applies a priority queue to relax the path cost, similar to the Bellman-Ford technique. Each grid cell is checked for possible direction changes, and the priority queue sorts cells based on their path cost, ensuring the optimal cost transit is prioritized.
C#
Time complexity is O(m * n * log(m * n)), similar to Dijkstra’s execution over a grid, and space complexity is O(m * n) due to the cost matrix and priority queue storage.
| Approach | Complexity |
|---|---|
| Dijkstra-like BFS Using Priority Queue | Time complexity is O(m*n), where m and n are the dimensions of the grid, due to each cell being processed in constant time with respect to its neighbors. Space complexity is also O(m*n) due to the storage required for maintaining the costs of each cell. |
| Bellman-Ford-like Relaxation Approach | Time complexity is O(m * n * log(m * n)), similar to Dijkstra’s execution over a grid, and space complexity is O(m * n) due to the cost matrix and priority queue storage. |
Minimum Cost to Make at Least One Valid Path in a Grid - Leetcode 1368 - Python • NeetCodeIO • 11,163 views views
Watch 9 more video solutions →Practice Minimum Cost to Make at Least One Valid Path in a Grid with our built-in code editor and test cases.
Practice on FleetCode