使网格图至少有一条有效路径的最小代价

题目

1368. 使网格图至少有一条有效路径的最小代价

---

给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：

• 1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]
• 2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]
• 3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]
• 4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]

注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域。

一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条 有效路径 为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径 不需要是最短路径 。

你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次 。

请你返回让网格图至少有一条有效路径的最小代价。

示例 1：

输入：grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
输出：3
解释：你将从点 (0, 0) 出发。
到达 (3, 3) 的路径为： (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) 花费代价 cost = 1 使方向向下 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) 花费代价 cost = 1 使方向向下 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) 花费代价 cost = 1 使方向向下 --> (3, 3)
总花费为 cost = 3.

示例 2：

输入：grid = [[1,1,3],[3,2,2],[1,1,4]]
输出：0
解释：不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。

示例 3：

输入：grid = [[1,2],[4,3]]
输出：1

示例 4：

输入：grid = [[2,2,2],[2,2,2]]
输出：3

示例 5：

输入：grid = [[4]]
输出：0

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100

题解

方法一：

思路

dijkstra

每个格子对于指向的格子连接一条边权为0的边，对于其他方向的格子连接一条边权为1的边，那么就是求(0,0)到(n-1,m-1)的最短路径。

题中说每个点只能修改一次也就是只能向非指向方向移动一次。但是对于最短路上每个点也只会经过一次，所以直接套最短路dijkstra即可。

代码

class Solution {
public:
    struct Node {
        int x, y;
        int val;
        bool operator<(const Node& o) const {
            return val > o.val;
        }
    };
    int dis[105][105];
    int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    int minCost(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        memset(dis, 0x3f, sizeof(dis));
        dis[0][0] = 0;
        priority_queue<Node> que;
        que.push({0,0,0});
        while (que.size()) {
            auto u = que.top(); que.pop();
            if (u.x == n-1 && u.y == m-1) return u.val;
            for (int i=0; i<4; i++) {
                int x = u.x+d[i][0];
                int y = u.y+d[i][1];
                int v = i+1 != grid[u.x][u.y];
                if (x<0 || x>=n || y<0 || y>=m || dis[x][y] <= dis[u.x][u.y]+v) continue;
                dis[x][y] = dis[u.x][u.y]+v;
                que.push({x, y, dis[x][y]});
            }
        }
        return -1;
    }
};

方法二：

思路

图中边权值为0或1

可用01BFS，求最短路

代码

class Solution {
public:
    int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    int minCost(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int dis[n][m];
        memset(dis, 0x3f, sizeof(dis));
        dis[0][0] = 0;
        deque<pair<int,int>> que;
        que.emplace_back(0,0);
        while (que.size()) {
            auto [u,v] = que.front(); que.pop_front();
            if (u == n-1 && v == m-1) return dis[u][v];
            for (int i=0; i<4; i++) {
                int x = u+d[i][0];
                int y = v+d[i][1];
                int val = i+1 != grid[u][v];
                if (x<0 || x>=n || y<0 || y>=m || dis[x][y] <= dis[u][v]+val) continue;
                dis[x][y] = dis[u][v]+val;
                if (val) que.emplace_back(x, y);
                else que.emplace_front(x, y);
            }
        }
        return -1;
    }
};