leetcode 6366. 在网格图中访问一个格子的最少时间
题目描述
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 | vector<pair<int,int>> turn={{0,1},{0,-1},{1,0},{-1,0}}; |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HeRen's Blog!
评论