最短路径问题 (6)

10.8 更多的 Leetcode 例题

Leetcode 1129. Shortest Path with Alternating Colors

https://leetcode.com/problems/shortest-path-with-alternating-colors/
题目大意：给一张有向图，每一条边可能着红色或着蓝色。请问从编号为 0 的点出发，到所有的点经过红蓝相间或蓝红相间的最短路径长度为何？
解题思考：我们可以用 Bellman-Ford 的方法，每一次扫过所有的边，并且更新「最後一条踏过蓝色边的最短路径」和「最後一条踏过红色边的最短路径」长度们。虽然这样执行时间复杂度是 O(mn)，但是相对好写一些。

class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
        int INF = 100*n;
        vector<int> blue_dist(n, INF);
        vector<int> red_dist(n, INF);
        blue_dist[0] = red_dist[0] = 0;
        for (int t = 0; t < n; t++) {
            for (auto e : red_edges)
                if (red_dist[e[1]] > blue_dist[e[0]] + 1)
                    red_dist[e[1]] = blue_dist[e[0]] + 1;
            for (auto e : blue_edges)
                if (blue_dist[e[1]] > red_dist[e[0]] + 1)
                    blue_dist[e[1]] = red_dist[e[0]] + 1;
        }
        vector<int> ret(n, -1);
        for (int i = 0; i < n; i++) {
            ret[i] = min(blue_dist[i], red_dist[i]);
            if (ret[i] >= INF) ret[i] = -1;
        }
        return ret;
    }
};

Leetcode 1091. Shortest Path in Binary Matrix

https://leetcode.com/problems/shortest-path-in-binary-matrix/
题目叙述：给你一个 n x n 的 0-1 矩阵，目的要从 (0, 0) 走到 (n-1, n-1)。每一次可以行进八方向的其中一格，问最短的全 0 路线长度为何。
解题思考：就是个八方向的 BFS。

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dist(n, vector<int>(n, -1));
        
        if (grid[0][0] == 1) return -1;
        dist[0][0] = 1;
        queue<pair<int, int>> Q;
        Q.push({0, 0});
        while (!Q.empty()) {
            auto it = Q.front(); Q.pop();
            int x = it.first; 
            int y = it.second;
            for (int dx = -1; dx <= 1; dx++)
                for (int dy = -1; dy <= 1; dy++) {
                    int nx = x + dx;
                    int ny = y + dy;
                    if (nx>=0 && nx<n && ny>=0 && ny<n && dist[nx][ny] == -1 && grid[nx][ny] == 0) {
                        dist[nx][ny] = dist[x][y] + 1;
                        Q.push({nx, ny});
                    }
                }
        }
        return dist[n-1][n-1];
    }
};