题目描述

leetcode 6366. 在网格图中访问一个格子的最少时间

给你一个 m x n 的矩阵 grid ，每个元素都为 非负 整数，其中 grid[row][col] 表示可以访问格子 (row, col) 的 最早 时间。也就是说当你访问格子 (row, col) 时，最少已经经过的时间为 grid[row][col] 。

你从 最左上角 出发，出发时刻为 0 ，你必须一直移动到上下左右相邻四个格子中的 任意 一个格子（即不能停留在格子上）。每次移动都需要花费 1 单位时间。

请你返回 最早 到达右下角格子的时间，如果你无法到达右下角的格子，请你返回 -1 。

 

示例 1：

输入：grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
输出：7
解释：一条可行的路径为：
- 时刻 t = 0 ，我们在格子 (0,0) 。
- 时刻 t = 1 ，我们移动到格子 (0,1) ，可以移动的原因是 grid[0][1] <= 1 。
- 时刻 t = 2 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 2 。
- 时刻 t = 3 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 3 。
- 时刻 t = 4 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 4 。
- 时刻 t = 5 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 5 。
- 时刻 t = 6 ，我们移动到格子 (1,3) ，可以移动的原因是 grid[1][3] <= 6 。
- 时刻 t = 7 ，我们移动到格子 (2,3) ，可以移动的原因是 grid[2][3] <= 7 。
最终到达时刻为 7 。这是最早可以到达的时间。

示例 2：

输入：grid = [[0,2,4],[3,2,1],[1,0,4]]
输出：-1
解释：没法从左上角按题目规定走到右下角。

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 1000
  • 4 <= m * n <= 105
  • 0 <= grid[i][j] <= 105
  • grid[0][0] == 0

题解——延时bfs，比较直白的方法

思路

如果没有时间限制，每次都可以到达相邻的格子，可以直接用bfs求解。也就是每次向外扩充一圈，将尚未访问的相邻点立即入队。
现在多了时间的限制，就会影响到入队的时间。比如说当前时间为2，而相邻点限制为4，则不能入队。对这种情况要经历一次来回，最终将在时间为5时访问那个点。
因此不难想到，虽然不能立即将它入队，但是我们可以知道它将在何时被访问，我们只要维护一个延时访问序列，并记录访问时间，在那个时候将它们入队即可。
我的方法是维护一个unordered_map<int,vector<pair<int,int>>>，记录将在time时刻被访问的序列。不过要注意一个问题，有可能有多个点通向某点，这时就要取最先访问的那条路，因此，还要记录某点最先访问的时刻，用一个firstIn数组记录即可，只有在二者匹配时，才入队。
时间消耗大概在400ms左右。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
vector<pair<int,int>> turn={{0,1},{0,-1},{1,0},{-1,0}};
class Solution {
public:
    int minimumTime(vector<vector<int>>& grid) {
        if(grid[0][1]>1&&grid[1][0]>1)//只有这种情况不能到右下角，否则总是能来回动
            return -1;
        int time=0,m=grid.size(),n=grid[0].size();
        vector<vector<int>> firstIn(m,vector<int>(n,INT_MAX));//维护首次入队时间
        map<int,vector<pair<int,int>>> memo;//维护延时入队序列
        queue<pair<int,int>> q;
        q.push({0,0});
        firstIn[0][0]=0;
        while(!q.empty()||!memo.empty())//队列非空或者还有延迟访问序列
        {
            for(auto &[x,y]:memo[time])
                if(time==firstIn[x][y])
                    q.push({x,y});
            memo.erase(memo.find(time));
            if(q.empty())//当队列为空时，跳到下一个延时序列处
            {
                time=memo.begin()->first;
                continue;
            }
            int cnt=q.size();
            for(int i=0;i<cnt;++i)
            {
                int _x=q.front().first,_y=q.front().second;
                if(_x==m-1&&_y==n-1)//到达右下角，返回当前时间
                    return time;
                q.pop();
                for(auto &p:turn)
                {
                    int x=_x+p.first,y=_y+p.second;
                    if(!(x>=0&&x<m&&y>=0&&y<n))//越界
                        continue;
                    int inTime=grid[x][y]>time+1?((grid[x][y]-time)%2?grid[x][y]:grid[x][y]+1):time+1;//计算访问时间
                    if(inTime<firstIn[x][y])//比之前的更优，则更新
                        memo[inTime].push_back({x,y}),firstIn[x][y]=inTime;
                }
            }
            ++time;
        }
        return -1;
    }
};