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

https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/description/?envType=daily-question&envId=2025-01-18

Tag: 0-1 BFS

class Solution {
public:
    int dr[5] = {0, 0, 0, 1, -1};
    int dc[5] = {0, 1, -1, 0, 0};
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = INT_MAX;
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        deque<array<int, 3>> dq;
        dq.push_front({0, 0, 0});
        while (!dq.empty()) {
            auto [times, x, y] = dq.front();
            dq.pop_front();
            if (x == m - 1 && y == n - 1) {
                return times;
            }
            if (vis[x][y]) continue;
            vis[x][y] = true;
            for (int dir = 1; dir <= 4; dir++) {
                int nx = x + dr[dir];
                int ny = y + dc[dir];
                if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
                if (dir != grid[x][y]) {
                    dq.push_back({times + 1, nx, ny});
                } else {
                    dq.push_front({times, nx, ny});
                }
            }
        }
        return ans;
    }
};

本題其實可以容忍數據範圍到 m x n = 10^6 但是此題目沒有開到這麼大，所以其實這題可以有很多種解法。

這是我的第一個版本，這個版本的核心思想就是 DP，只要我把所有可能的更換次數都是過就會知道答案，並且更換次數其實不會超過 m + n ，因為我可以一路向左再一路向下。

class Solution {
public:
    int dr[5] = {0, 0, 0, 1, -1};
    int dc[5] = {0, 1, -1, 0, 0};
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = INT_MAX;
        vector<vector<vector<bool>>> vis(m + n, vector<vector<bool>>(m, vector<bool>(n, false)));
        queue<pair<int, pair<int, int>>> q;
        q.push({0, {0, 0}});
        while (!q.empty()) {
            auto [times, pos] = q.front();
            q.pop();
            auto [x, y] = pos;
            if (x == m - 1 && y == n - 1) {
                ans = min(ans, times);
            }
            if (times >= m + n) continue;
            if (vis[times][x][y]) continue;
            vis[times][x][y] = true;
            for (int dir = 1; dir <= 4; dir++) {
                int nx = x + dr[dir];
                int ny = y + dc[dir];
                if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
                q.push({times + (dir != grid[x][y]), {nx, ny}});
            }
        }
        return ans;
    }
};

第二種解法，這種解法的核心就是 Priority Queue，因為只要再觀察一下就可以發現把更換次數作為排序順序，那麼一但到過該點則該變換次數就會是最少變換次數。

class Solution {
public:
    int dr[5] = {0, 0, 0, 1, -1};
    int dc[5] = {0, 1, -1, 0, 0};
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = INT_MAX;
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
        pq.push({0, {0, 0}});
        while (!pq.empty()) {
            auto [times, pos] = pq.top();
            pq.pop();
            auto [x, y] = pos;
            if (x == m - 1 && y == n - 1) {
                return times;
            }
            if (vis[x][y]) continue;
            vis[x][y] = true;
            for (int dir = 1; dir <= 4; dir++) {
                int nx = x + dr[dir];
                int ny = y + dc[dir];
                if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
                pq.push({times + (dir != grid[x][y]), {nx, ny}});
            }
        }
        return ans;
    }
};

最後一個版本就是最上面給的 Code，因為我們可以發現每次加變換次數都只會加 1 所以其實符合 0-1 BFS 的規律，那我們就可以把 Priority Queue 改成 Deque 就可以。

最終我們的複雜度就只剩下 O(m * n) 舒服。