Minimum Cost to Make at Least One Valid Path in a Grid

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int dx[5] = {0, 0, 0, 1, -1}, dy[5] = {0, 1, -1, 0, 0};
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        dist[0][0] = 0;
        deque<pair<int,int>> dq;
        dq.push_front({0, 0});
        while (!dq.empty()) {
            auto [r, c] = dq.front(); dq.pop_front();
            for (int d = 1; d <= 4; ++d) {
                int nr = r + dx[d], nc = c + dy[d];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                int w = (grid[r][c] == d) ? 0 : 1;
                int nd = dist[r][c] + w;
                if (nd < dist[nr][nc]) {
                    dist[nr][nc] = nd;
                    if (w == 0) dq.push_front({nr, nc});
                    else dq.push_back({nr, nc});
                }
            }
        }
        return dist[m - 1][n - 1];
    }
};

func minCost(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    dx := [5]int{0, 0, 0, 1, -1}
    dy := [5]int{0, 1, -1, 0, 0}
    dist := make([][]int, m)
    for i := range dist {
        dist[i] = make([]int, n)
        for j := range dist[i] {
            dist[i][j] = math.MaxInt32
        }
    }
    dist[0][0] = 0
    type cell struct{ r, c int }
    dq := []cell{{0, 0}}
    for len(dq) > 0 {
        cur := dq[0]
        dq = dq[1:]
        r, c := cur.r, cur.c
        for d := 1; d <= 4; d++ {
            nr, nc := r+dx[d], c+dy[d]
            if nr < 0 || nr >= m || nc < 0 || nc >= n {
                continue
            }
            w := 1
            if grid[r][c] == d {
                w = 0
            }
            nd := dist[r][c] + w
            if nd < dist[nr][nc] {
                dist[nr][nc] = nd
                if w == 0 {
                    dq = append([]cell{{nr, nc}}, dq...)
                } else {
                    dq = append(dq, cell{nr, nc})
                }
            }
        }
    }
    return dist[m-1][n-1]
}

from typing import List
from collections import deque

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dx = [0, 0, 0, 1, -1]
        dy = [0, 1, -1, 0, 0]
        INF = float('inf')
        dist = [[INF] * n for _ in range(m)]
        dist[0][0] = 0
        dq = deque([(0, 0)])
        while dq:
            r, c = dq.popleft()
            for d in range(1, 5):
                nr, nc = r + dx[d], c + dy[d]
                if nr < 0 or nr >= m or nc < 0 or nc >= n:
                    continue
                w = 0 if grid[r][c] == d else 1
                nd = dist[r][c] + w
                if nd < dist[nr][nc]:
                    dist[nr][nc] = nd
                    if w == 0:
                        dq.appendleft((nr, nc))
                    else:
                        dq.append((nr, nc))
        return dist[m - 1][n - 1]

function minCost(grid) {
    const m = grid.length, n = grid[0].length;
    const dx = [0, 0, 0, 1, -1];
    const dy = [0, 1, -1, 0, 0];
    const dist = Array.from({ length: m }, () => new Array(n).fill(Infinity));
    dist[0][0] = 0;
    const dq = [[0, 0]];
    while (dq.length) {
        const [r, c] = dq.shift();
        for (let d = 1; d <= 4; d++) {
            const nr = r + dx[d], nc = c + dy[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            const w = grid[r][c] === d ? 0 : 1;
            const nd = dist[r][c] + w;
            if (nd < dist[nr][nc]) {
                dist[nr][nc] = nd;
                if (w === 0) dq.unshift([nr, nc]);
                else dq.push([nr, nc]);
            }
        }
    }
    return dist[m - 1][n - 1];
}

class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dx = {0, 0, 0, 1, -1};
        int[] dy = {0, 1, -1, 0, 0};
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        dist[0][0] = 0;
        ArrayDeque<int[]> dq = new ArrayDeque<>();
        dq.offerFirst(new int[]{0, 0});
        while (!dq.isEmpty()) {
            int[] cur = dq.pollFirst();
            int r = cur[0], c = cur[1];
            for (int d = 1; d <= 4; d++) {
                int nr = r + dx[d], nc = c + dy[d];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                int w = (grid[r][c] == d) ? 0 : 1;
                int nd = dist[r][c] + w;
                if (nd < dist[nr][nc]) {
                    dist[nr][nc] = nd;
                    if (w == 0) dq.offerFirst(new int[]{nr, nc});
                    else dq.offerLast(new int[]{nr, nc});
                }
            }
        }
        return dist[m - 1][n - 1];
    }
}

function minCost(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const dx = [0, 0, 0, 1, -1];
    const dy = [0, 1, -1, 0, 0];
    const dist: number[][] = Array.from({ length: m }, () => new Array<number>(n).fill(Infinity));
    dist[0][0] = 0;
    const dq: [number, number][] = [[0, 0]];
    while (dq.length) {
        const [r, c] = dq.shift()!;
        for (let d = 1; d <= 4; d++) {
            const nr = r + dx[d], nc = c + dy[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            const w = grid[r][c] === d ? 0 : 1;
            const nd = dist[r][c] + w;
            if (nd < dist[nr][nc]) {
                dist[nr][nc] = nd;
                if (w === 0) dq.unshift([nr, nc]);
                else dq.push([nr, nc]);
            }
        }
    }
    return dist[m - 1][n - 1];
}