题目描述
给你一个 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
的代价修改一个格子中的数字,但每个格子中的数字 只能修改一次。
请你返回让网格图至少有一条有效路径的最小代价。
样例
输入: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
输入:grid = [[1,1,3],[3,2,2],[1,1,4]]
输出:0
解释:不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。
输入:grid = [[1,2],[4,3]]
输出:1
输入:grid = [[2,2,2],[2,2,2]]
输出:3
输入:grid = [[4]]
输出:0
限制
m == grid.length
n == grid[i].length
1 <= m, n <= 100
算法
(宽度优先搜索) $O(mn)$
- 容易发现这是个边权为 0 或 1 的最短路问题。如果我们要改变一个格子的方向,则边权为 1;否则边权就是 0。
- 解 01 最短路可以采用双端队列形式的宽度优先搜索。根据 Dijkstra 的最短路算法,我们需要保证的是队头的元素永远都是最小值,但我们不必使用优先级队列。我们可以采用双端队列,如果新的点是以边权为 0 被更新的,则入到队头;否则入到队尾。
- 剩下的更新就是普通的宽度优先搜索的操作了。
思考:如果边权改为 1 或 2,是否还能用双端队列解呢?
时间复杂度
- 每个位置仅访问一次,故时间复杂度为 $O(mn)$。
空间复杂度
- 需要额外 $O(mn)$ 的空间存储队列和距离数组。
C++ 代码
class Solution {
public:
int minCost(vector<vector<int>>& grid) {
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
int m = grid.size(), n = grid[0].size();
deque<pair<int, int>> q;
vector<vector<int>> cost(m, vector<int>(n, m * n));
q.emplace_back(0, 0);
cost[0][0] = 0;
while (!q.empty()) {
auto u = q.front();
q.pop_front();
for (int i = 0; i < 4; i++) {
int x = u.first + dx[i], y = u.second + dy[i];
int c = int(i != grid[u.first][u.second] - 1);
if (x < 0 || x >= m || y < 0 || y >= n)
continue;
if (cost[x][y] > cost[u.first][u.second] + c) {
cost[x][y] = cost[u.first][u.second] + c;
if (c == 0) q.emplace_front(x, y);
else q.emplace_back(x, y);
}
}
}
return cost[m - 1][n - 1];
}
};
01最短路模板题https://www.acwing.com/problem/content/177/
dl