最短路径问题 (2)

10.3 几个简单的 Leetcode 例题

如果边的权重都相等，那麽使用 BFS 就可以为我们找出最短的路径了。
今天来讲讲简单的最短路径例题吧。
这几个例子都是透过建构一张图，并且在上面计算最短路径。

Leetcode 1293. Shortest Path in a Grid with Obstacles Elimination

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

题目大意：给你一个 M * N 的格点，你想要从左上角的 (0, 0) 走到右下角的 (m-1, n-1)。格子内若标记为 1 代表有障碍物，标记为 0 则为空地。若只能消除不超过 K 个障碍物，请问至少得走几步才能从左上走到右下呢？

解题想法：我们可以将 "消除了多少障碍物" 这个条件加入图中。将每一个格子与目前已消除的障碍物数量当作一个图上的节点 (k, x, y)，若相邻的格子 (x’, y’) 有障碍物，则建立一条边连至 (k+1, x’, y’)，否则连至 (k, x’, y’)。最终求得 (0, 0, 0) 走到 min_{k’<=k}{ (k’, m-1, n-1) } 的最短路径。
时间复杂度是 O(kmn)，空间也需要 O(kmn)。

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        int dist[1605][50][50];
        memset(dist, -1, sizeof(dist));
        
        queue<int> Q;
        Q.push(0); Q.push(0); Q.push(0); dist[0][0][0] = 0;
        while (!Q.empty()) {
            int l = Q.front(); Q.pop();
            int x = Q.front(); Q.pop();
            int y = Q.front(); Q.pop();
            int dx[4] = {-1, 0, 1, 0};
            int dy[4] = {0, 1, 0, -1};
            if (x == m-1 && y == n-1) return dist[l][x][y];
            for (int f = 0; f < 4; f++) {
                int nx = x + dx[f];
                int ny = y + dy[f];
                if (nx>=0 && nx<m && ny>=0 && ny<n) {
                    if (l < k && grid[nx][ny] == 1 && dist[l+1][nx][ny] == -1) {
                        dist[l+1][nx][ny] = dist[l][x][y] + 1;
                        Q.push(l+1); Q.push(nx); Q.push(ny);
                    } else if (grid[nx][ny] == 0 && dist[l][nx][ny] == -1) {
                        dist[l][nx][ny] = dist[l][x][y] + 1;
                        Q.push(l); Q.push(nx); Q.push(ny);
                    }
                }
            }
        }
        return -1;
    }
};

Leetcode 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/

题目大意：给你一个 M * N 的格子点，每一格上面有个箭头。你想要从 (0, 0) 走到 (m-1, n-1)，但是你只能顺着箭头方向前进。你的目标是将最少数量的格子内的箭头变换方向，使得你能够走完整条路径。求最少的箭头改变次数。

解题想法：这题跟前一题很像，但不太一样。我们只需要对每一个格子建立一个点，但是格子与格子之间的边，可能是免费、可能要花 1 单位的花费，所以是有权重的。在这种边权重仅仅是 0 或 1 的特殊情形下，我们仍然可以用类似 BFS 的方式来找出答案：优先处理边权重是 0 的那些格子。

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int dist[105][105];
        memset(dist, -1, sizeof(dist));
        deque<pair<int, int>> Q;
        Q.push_back({0, 0});
        dist[0][0] = 0;
        while (!Q.empty()) {
            auto p = Q.front(); Q.pop_front();
            int x = p.first;
            int y = p.second;
            const int dx[4] = {0, 0, 1, -1};
            const int dy[4] = {1, -1, 0, 0};
            for(int f = 0; f < 4; f++) {
                int nx = x + dx[f];
                int ny = y + dy[f];
                if (nx>=0 && nx<m && ny>=0 && ny<n) {
                    if (grid[x][y] == f+1 && (dist[nx][ny] == -1 || dist[nx][ny] > dist[x][y])) {
                        dist[nx][ny] = dist[x][y];
                        Q.push_front({nx, ny});
                    } else if (grid[x][y] != f+1 && (dist[nx][ny] == -1 || dist[nx][ny] > dist[x][y] + 1)) {
                        dist[nx][ny] = dist[x][y] + 1;
                        Q.push_back({nx, ny});
                    }
                }
            }
        }
        
        return dist[m-1][n-1];
    }
};