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 fromgrid[i][j]
togrid[i][j + 1]
)2
which means go to the cell to the left. (i.e go fromgrid[i][j]
togrid[i][j - 1]
)3
which means go to the lower cell. (i.e go fromgrid[i][j]
togrid[i + 1][j]
)4
which means go to the upper cell. (i.e go fromgrid[i][j]
togrid[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.
Examples
Example 1:
$$ \begin{matrix} \rightarrow & \rightarrow & \rightarrow & \rightarrow \\ \leftarrow & \leftarrow & \leftarrow & \leftarrow \\ \rightarrow & \rightarrow & \rightarrow & \rightarrow \\ \leftarrow & \leftarrow & \leftarrow & \leftarrow \\ \end{matrix} $$
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:
$$ \begin{matrix} \rightarrow & \rightarrow & \downarrow \\ \downarrow & \leftarrow & \leftarrow \\ \rightarrow & \rightarrow & \uparrow \\ \end{matrix} $$
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:
$$ \begin{matrix} \rightarrow & \leftarrow \\ \uparrow & \downarrow \\ \end{matrix} $$
Input: grid = [[1,2],[4,3]]
Output: 1
Solution
Method 1 - Using Dijkstra Algorithm
To solve the problem of finding the minimum cost to make the grid have at least one valid path, we can use a shortest path algorithm like Dijkstra’s but slightly modified. The grid can be considered as a weighted graph where:
- Nodes represent grid cells.
- Edges between nodes represent possible moves between cells, with weights being the cost of modifying the signs.
Approach
- Define the direction vectors for moving right, left, down, and up.
- Use a priority queue (min-heap) to always expand the least cost cell first.
- Initialise the distance to reach each cell as infinity, except for the starting cell which is 0.
- Use the priority queue to explore the neighbors of the current cell.
- Calculate the cost to move to each neighbor. If it follows the current cell’s direction, the cost is 0, otherwise it is 1.
- Update the distance and push the neighbor to the queue if a shorter path is found.
- Continue until reaching the bottom-right cell.
- The final answer will be the distance to the bottom-right cell.
Code
Java
class Solution {
public int minCost(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int[][] dist = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
}
dist[0][0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, 0, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int cost = curr[0], i = curr[1], j = curr[2];
if (i == m - 1 && j == n - 1) {
return cost;
}
for (int idx = 0; idx < 4; idx++) {
int ni = i + directions[idx][0], nj = j + directions[idx][1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
int newCost = cost + (grid[i][j] != idx + 1 ? 1 : 0);
if (newCost < dist[ni][nj]) {
dist[ni][nj] = newCost;
pq.offer(new int[]{newCost, ni, nj});
}
}
}
}
return dist[m - 1][n - 1];
}
}
Python
class Solution:
def minCost(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
pq: List[Tuple[int, int, int]] = [(0, 0, 0)] # (cost, row, col)
dist = [[float('inf')] * n for _ in range(m)]
dist[0][0] = 0
while pq:
cost, i, j = heappop(pq)
if (i, j) == (m - 1, n - 1):
return cost
for idx, (di, dj) in enumerate(directions):
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n:
new_cost = cost + (grid[i][j] != idx + 1)
if new_cost < dist[ni][nj]:
dist[ni][nj] = new_cost
heappush(pq, (new_cost, ni, nj))
return dist[m - 1][n - 1]
Complexity
- ⏰ Time complexity:
O(m * n * log(m * n))
due to the use of a priority queue where every node is processed once. - 🧺 Space complexity:
O(m * n)
for storing distances and the priority queue.