You are given a m x n grid where each cell contains a value from 1 to 4. Each value represents a direction:
1 - right2 - left3 - down4 - up(0, 0), your goal is to reach the bottom-right cell (m-1, n-1) by following a path. You can move to an adjacent cell in the direction indicated by the current cell at no cost. If you want to move in a different direction, you must change the arrow in the current cell, incurring a cost of 1 for each change.
(0,0) to (m-1,n-1).1.
At first glance, you might consider brute-forcing all possible paths from the start to the end, changing directions as needed and accumulating the cost for each change. However, this approach quickly becomes infeasible as the grid grows in size due to the exponential number of possible paths.
Instead, notice that each move in the direction indicated by the cell is "free" (cost 0), while moving in another direction requires a "change" (cost 1). This suggests modeling the problem as a shortest path search with edge weights of 0 or 1 depending on whether you follow the arrow or need to change it.
The optimal approach is to use a modified BFS (Breadth-First Search) that accounts for edge weights, often called 0-1 BFS. This allows us to always expand the lowest-cost paths first, ensuring we find the minimum cost to reach the bottom-right cell.
To solve the problem efficiently, we treat the grid as a graph where each cell is a node. Moving in the indicated direction has a cost of 0, while moving in any other direction has a cost of 1. We use a double-ended queue (deque) to perform a 0-1 BFS:
cost where cost[i][j] is the minimum cost to reach cell (i, j).
Input:
grid = [
[1, 1, 3],
[3, 2, 2],
[1, 1, 4]
]
Step-by-step:
(0,0) where the arrow points right. Move to (0,1) at cost 0.
(0,1), arrow points right. Move to (0,2) at cost 0.
(0,2), arrow points down. Move to (1,2) at cost 0.
(1,2), arrow points left. The only way forward is to change the arrow to point down (cost 1) and move to (2,2).
(2,2), we have reached the bottom-right cell. The minimum cost is 1.
Brute-force Approach:
O(m*n), since each cell is processed at most once per cost value, and there are m*n cells.
O(m*n) for the cost array and queue.
The key insight is to treat the grid as a graph and use a shortest-path algorithm tailored for 0-1 edge weights (0-1 BFS). By always moving in the cell's indicated direction when possible, and only changing direction when necessary, we minimize the total cost. This approach is both time and space efficient, and elegantly solves the problem by leveraging graph traversal techniques.
from collections import deque
class Solution:
def minCost(self, grid):
m, n = len(grid), len(grid[0])
dirs = [(0,1), (0,-1), (1,0), (-1,0)] # right, left, down, up
cost = [[float('inf')] * n for _ in range(m)]
cost[0][0] = 0
dq = deque()
dq.append((0, 0))
while dq:
x, y = dq.popleft()
for i, (dx, dy) in enumerate(dirs):
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
# If moving in the direction of the arrow, cost is 0; else 1
ncost = cost[x][y] + (0 if grid[x][y] == i + 1 else 1)
if ncost < cost[nx][ny]:
cost[nx][ny] = ncost
if grid[x][y] == i + 1:
dq.appendleft((nx, ny))
else:
dq.append((nx, ny))
return cost[m-1][n-1]
#include <vector>
#include <deque>
#include <climits>
using namespace std;
class Solution {
public:
int minCost(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> cost(m, vector<int>(n, INT_MAX));
vector<pair<int, int>> dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
deque<pair<int, int>> dq;
cost[0][0] = 0;
dq.push_back({0,0});
while (!dq.empty()) {
auto [x, y] = dq.front(); dq.pop_front();
for (int i = 0; i < 4; ++i) {
int nx = x + dirs[i].first, ny = y + dirs[i].second;
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int ncost = cost[x][y] + (grid[x][y] == i+1 ? 0 : 1);
if (ncost < cost[nx][ny]) {
cost[nx][ny] = ncost;
if (grid[x][y] == i+1)
dq.push_front({nx, ny});
else
dq.push_back({nx, ny});
}
}
}
}
return cost[m-1][n-1];
}
};
import java.util.*;
class Solution {
public int minCost(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] cost = new int[m][n];
for (int[] row : cost) Arrays.fill(row, Integer.MAX_VALUE);
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
Deque<int[]> dq = new ArrayDeque<>();
cost[0][0] = 0;
dq.offerFirst(new int[]{0,0});
while (!dq.isEmpty()) {
int[] cell = dq.pollFirst();
int x = cell[0], y = cell[1];
for (int i = 0; i < 4; ++i) {
int nx = x + dirs[i][0], ny = y + dirs[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int ncost = cost[x][y] + (grid[x][y] == i+1 ? 0 : 1);
if (ncost < cost[nx][ny]) {
cost[nx][ny] = ncost;
if (grid[x][y] == i+1)
dq.offerFirst(new int[]{nx, ny});
else
dq.offerLast(new int[]{nx, ny});
}
}
}
}
return cost[m-1][n-1];
}
}
/**
* @param {number[][]} grid
* @return {number}
*/
var minCost = function(grid) {
const m = grid.length, n = grid[0].length;
const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
const cost = Array.from({length: m}, () => Array(n).fill(Infinity));
cost[0][0] = 0;
const deque = [];
deque.push([0, 0]);
while (deque.length) {
const [x, y] = deque.shift();
for (let i = 0; i < 4; ++i) {
const nx = x + dirs[i][0], ny = y + dirs[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
const ncost = cost[x][y] + (grid[x][y] === i + 1 ? 0 : 1);
if (ncost < cost[nx][ny]) {
cost[nx][ny] = ncost;
if (grid[x][y] === i + 1)
deque.unshift([nx, ny]);
else
deque.push([nx, ny]);
}
}
}
}
return cost[m-1][n-1];
};