Problem Explanation

You are given a grid with certain directions on each cell. The goal is to make a path from the top left cell of the grid to the bottom right cell. We can modify the direction of a cell with a cost of 1, and we want to minimize the total cost to make a valid path.

The initial directions are numbered from 1-4, each representing direction as follows:

1: Move Right 2: Move Left 3: Move Down 4: Move Up

Your task is to calculate the minimum number of changes required to get from the top left of the grid to the bottom right. This doesn't have to be the shortest path.

Solution Approach

The solution uses a breadth-first search (BFS) algorithm and a dynamic programming approach. BFS traverses horizontally first in a grid before moving down (or up), which is perfect for this problem because changing a cell direction incurs a cost, and we want to minimize the cost.

We start the BFS from the top-left cell (0,0) and follow the cells' direction (without incurring any cost) and store the low-cost path in a DP table. The grid cells reached without any modification are pushed into a queue.

The process continues until no more cells can be reached. If we haven't reached the bottom-right cell, we pop a cell from the queue, change its direction, update the DP table, and enqueue all reachable, unvisited cells. The popped cell will have the lowest cost among all cells in the queue, thanks to the property of BFS.

Python Solution:

1
2python
3from collections import deque
4class Solution:
5    def minCost(self, grid) -> int:
6        dir = [(0,1), (0,-1), (1,0), (-1,0)]
7        m, n = len(grid), len(grid[0])
8        dp = [[float('inf')]*n for _ in range(m)]
9        dp[0][0] = 0
10        dq = deque([(0,0)])
11        while dq:
12            x, y = dq.popleft()
13            for i in range(4):
14                nx, ny = x + dir[i][0], y + dir[i][1]
15                if nx < 0 or ny < 0 or nx >= m or ny >= n: continue
16                cost = dp[x][y] if i == grid[x][y] - 1 else dp[x][y] + 1
17                if cost < dp[nx][ny]:
18                    dp[nx][ny] = cost
19                    if i == grid[x][y] - 1: dq.appendleft((nx, ny))
20                    else: dq.append((nx, ny))
21        return dp[m-1][n-1]

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int minCost(vector<vector<int>>& grid) {
6        vector<pair<int, int>> d = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
7        int m = grid.size(), n = grid[0].size();
8        vector<vector<int>> dp(m, vector<int>(n, 2000));
9        deque<pair<int, int>> dq({{0, 0}});
10        dp[0][0] = 0;
11        while (!dq.empty()) {
12            auto [x, y] = dq.front(); dq.pop_front();
13            for (int i = 0; i < 4; ++i) {
14                int nx = x + d[i].first, ny = y + d[i].second;
15                if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
16                int cost = dp[x][y] + (grid[x][y] != i + 1);
17                if (cost < dp[nx][ny]) {
18                    if (grid[x][y] != i + 1) dq.push_back({nx, ny});
19                    else dq.push_front({nx, ny});
20                    dp[nx][ny] = cost;
21                }
22            }
23        }
24        return dp[m - 1][n - 1];
25    }
26};

The solutions in Java and JavaScript are coming up next.# Java Solution:

1
2java
3import java.util.*;
4
5class Solution {
6    public int minCost(int[][] grid) {
7        int m = grid.length, n = grid[0].length;
8        int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
9        int[][] dp = new int[m][n];
10        for (int i=0; i<m; ++i) {
11            Arrays.fill(dp[i], Integer.MAX_VALUE);
12        }
13        
14        Deque<int[]> dq = new ArrayDeque<>();
15        dq.offerFirst(new int[]{0, 0, 0});
16        while (!dq.isEmpty()) {
17            int[] info = dq.pollFirst();
18            int x = info[0], y = info[1], cost = info[2];
19            if (x < 0 || y < 0 || x >= m || y >= n || dp[x][y] <= cost) continue;
20            dp[x][y] = cost;
21            for (int i = 0; i < 4; ++i) {
22                int nx = x + dir[i][0];
23                int ny = y + dir[i][1];
24                if (i + 1 == grid[x][y]) {
25                    dq.offerFirst(new int[]{nx, ny, cost});
26                } else {
27                    dq.offerLast(new int[]{nx, ny, cost + 1});
28                }
29            }
30        }
31        return dp[m-1][n-1];
32    }
33}

JavaScript Solution:

1
2javascript
3var minCost = function(grid) {
4    const m = grid.length, n = grid[0].length;
5    const dir = [[0,1],[0,-1],[1,0],[-1,0]];
6    const dp = Array.from({ length: m }, () => Array(n).fill(Infinity));
7    const dq = [[0, 0, 0]];
8    while (dq.length) {
9        const [x, y, cost] = dq.shift();
10        if (x < 0 || y < 0 || x >= m || y >= n || dp[x][y] <= cost) continue;
11        dp[x][y] = cost;
12        for (let i = 0; i < 4; i++) {
13            const nx = x + dir[i][0], ny = y + dir[i][1];
14            if (i + 1 === grid[x][y]) dq.unshift([nx, ny, cost]);
15            else dq.push([nx, ny, cost + 1]);
16        }
17    }
18    return dp[m-1][n-1];
19};

In all of these solutions, we store the minimum transformation cost for each cell in the dynamic programming table dp. We continue the BFS and queue manipulation until all reachable cells are visited. These solutions are efficient and exhibit time complexity of O(mn), where m and n are the dimensions of the grid. The space complexity is also O(mn) due to the space required for the dynamic programming table and the queue of the BFS.