全国建设网站,如何写软文,买东西最便宜的软件,赣州新闻联播直播在网格图中访问一个格子的最少时间
题目描述
给你一个 m x n 的矩阵 grid #xff0c;每个元素都为 非负 整数#xff0c;其中 grid[row][col] 表示可以访问格子 (row, col) 的 最早 时间。也就是说当你访问格子 (row, col) 时#xff0c;最少已经经过的时间为 grid[row][…在网格图中访问一个格子的最少时间
题目描述
给你一个 m x n 的矩阵 grid 每个元素都为 非负 整数其中 grid[row][col] 表示可以访问格子 (row, col) 的 最早 时间。也就是说当你访问格子 (row, col) 时最少已经经过的时间为 grid[row][col] 。
你从 最左上角 出发出发时刻为 0 你必须一直移动到上下左右相邻四个格子中的 任意 一个格子即不能停留在格子上。每次移动都需要花费 1 单位时间。
请你返回 最早 到达右下角格子的时间如果你无法到达右下角的格子请你返回 -1 。
样例
样例输入 grid [[0,1,3,2],[5,1,2,5],[4,3,8,6]] grid [[0,2,4],[3,2,1],[1,0,4]] 样例输出 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 。这是最早可以到达的时间。 -1 解释没法从左上角按题目规定走到右下角。 提示
m grid.length$ngrid[i].lengthn grid[i].lengthngrid[i].length2m,n10002 m, n 10002m,n10004m∗n1054 m * n 10^54m∗n1050grid[i][j]1050 grid[i][j] 10^50grid[i][j]105grid[0][0]0grid[0][0] 0grid[0][0]0
思路
题目还是昨天那个但这是另一个方法单调性还是很好看出来的num越大越能从重点走到起点反之越小越不能走到起点。然后就是check函数的可行性简单分析后也是具有可行性。
代码实现
class Solution {int[][] dir {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};private int[][] grid, vis;int m, n;public int minimumTime(int[][] grid) {if(grid[1][0] 1 grid[0][1] 1) return -1;this.grid grid;m grid.length;n grid[0].length;vis new int[m][n];int l Math.max(grid[m-1][n-1], m n - 2);int r (int)1e5 m n;while(l r){int mid (l r) 1;if(check(mid)) r mid;else l mid 1;}return l (l m n) % 2;}private boolean check(int num){// 不知道为什么使用queue会超出空间使用范围。vis[m - 1][n - 1] num;var q new ArrayListint[]();q.add(new int[]{m - 1, n - 1});for(int t num - 1; !q.isEmpty(); t--){var tmp q;q new ArrayListint[]();for(var cur : tmp){int i cur[0], j cur[1];for(var di : dir){int x i di[0], y j di[1];if(0 x x m 0 y y n vis[x][y] ! num grid[x][y] t){if(x 0 y 0) return true;q.add(new int[]{x, y});vis[x][y] num;}}}}return false;}
}
