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];
    }
};