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

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    using TII = tuple<int, int, int>;
public:
    int minCost(vector<vector<int>>& grid) {
        // 1->right, 2->left, 3->down, 4->up.
        int m = grid.size(), n = grid[0].size(), ds[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        vector<vector<int>> dist(m, vector<int>(n, 0x3f3f3f3f));
        vector<vector<bool>> vis(m, vector<bool>(n));
        dist[0][0] = 0;
        priority_queue<TII, vector<TII>, greater<TII>> q;
        q.emplace(0, 0, 0);
        while (q.size()) {
            auto [d, x, y] = q.top(); q.pop();
            if (vis[x][y]) continue;
            vis[x][y] = true;
            for (int i = 0; i < 4; ++i) {
                int nx = x + ds[i][0], ny = y + ds[i][1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                int w = grid[x][y] != i + 1;
                if (dist[nx][ny] > dist[x][y] + w) {
                    dist[nx][ny] = dist[x][y] + w;
                    q.emplace(dist[nx][ny], nx, ny);
                }
            }
        }
        return dist[m - 1][n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        // 1->right, 2->left, 3->down, 4->up.
        int m = grid.size(), n = grid[0].size(), ds[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        vector<vector<int>> dist(m, vector<int>(n, 0x3f3f3f3f));
        // vector<vector<bool>> vis(m, vector<bool>(n));
        dist[0][0] = 0;
        deque<pair<int, int>> q;
        q.emplace_back(0, 0);
        while (q.size()) {
            auto [x, y] = q.front(); q.pop_front();
            // if (vis[x][y]) continue;
            // vis[x][y] = true;
            for (int i = 0; i < 4; ++i) {
                int nx = x + ds[i][0], ny = y + ds[i][1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                int w = grid[x][y] != i + 1;
                if (dist[nx][ny] > dist[x][y] + w) {
                    dist[nx][ny] = dist[x][y] + w;
                    if (w) q.emplace_back(nx, ny);
                    else q.emplace_front(nx, ny);
                }
            }
        }
        return dist[m - 1][n - 1];
    }
};