从Leetcode 每日一题练习继续讨论：
2577. 在网格图中访问一个格子的最少时间
2577. Minimum Time to Visit a Cell In a Grid
题解
本题仍可以使用dijistra算法解决，像昨天的问题一样，将每个位置视为节点，只不过将每个位置对应的时间视为到这个节点的总成本，同时因为可以在两个节点间来回移动直到时间足够能移动到下一个节点，则只要能从原始位置通过一个时间间隔移动到相邻的位置就可以通过来回移动直到时间足够能移动到下一个相邻可移动位置。但要注意，在来回移动的时候要想继续向当前位置的下一个相邻位置移动，需要移动偶数次步数，因为奇数次步数会移动回当前位置的前一个位置，偶数才会移动回当前位置。
在最开始，只要能从初始位置移动到相邻位置，后面就可以使用dijistra找到到达右下角的最短路径。
代码
class Solution {
public:
int minimumTime(vector<vector<int>>& grid) {
// 如果一开始就无法移动，直接返回-1
if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
dist[0][0] = 0;
vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
priority_queue<pair<int, pair<int, int>>,
vector<pair<int, pair<int, int>>>,
greater<>> pq;
pq.push({0, {0, 0}});
while (!pq.empty()) {
auto [time, pos] = pq.top();
auto [x, y] = pos;
pq.pop();
if (time > dist[x][y]) continue;
for (const auto& dir : dirs) {
int nx = x + dir.first;
int ny = y + dir.second;
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int nextTime = time + 1;
// 需要等待到满足要求的时间
if (grid[nx][ny] > nextTime) {
// 如果时间差是奇数，需要多等一步
nextTime = grid[nx][ny];
if ((grid[nx][ny] - time) % 2 == 0) {
nextTime++;
}
}
if (nextTime < dist[nx][ny]) {
dist[nx][ny] = nextTime;
pq.push({nextTime, {nx, ny}});
}
}
}
}
return dist[m-1][n-1] == INT_MAX ? -1 : dist[m-1][n-1];
}
};