列表

详情

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
解释：没法从左上角按题目规定走到右下角。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int minimumTime(vector<vector<int>>& grid) { } };

python3 解法, 执行用时: 5668 ms, 内存消耗: 26 MB, 提交时间: 2023-02-27 14:33:44 

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        if grid[0][1] > 1 and grid[1][0] > 1:  # 无法「等待」
            return -1

        vis = [[-inf] * n for _ in range(m)]
        def check(end_time: int) -> bool:
            vis[-1][-1] = end_time
            q = [(m - 1, n - 1)]
            t = end_time - 1
            while q:
                tmp = q
                q = []
                for i, j in tmp:
                    for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 枚举周围四个格子
                        if 0 <= x < m and 0 <= y < n and vis[x][y] != end_time and grid[x][y] <= t:
                            if x == 0 and y == 0: return True
                            vis[x][y] = end_time  # 用二分的值来标记，避免重复创建 vis 数组
                            q.append((x, y))
                t -= 1
            return False

        left = max(grid[-1][-1], m + n - 2) - 1
        right = max(map(max, grid)) + m + n  # 开区间
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid): right = mid
            else: left = mid
        return right + (right - m - n) % 2

java 解法, 执行用时: 320 ms, 内存消耗: 53.7 MB, 提交时间: 2023-02-27 14:33:27 

class Solution {
    private final static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int[][] grid, vis;

    public int minimumTime(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid[0][1] > 1 && grid[1][0] > 1) // 无法「等待」
            return -1;

        this.grid = grid;
        vis = new int[m][n];
        int left = Math.max(grid[m - 1][n - 1], m + n - 2) - 1;
        int right = (int) 1e5 + m + n; // 开区间
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(mid)) right = mid;
            else left = mid;
        }
        return right + (right + m + n) % 2;
    }

    private boolean check(int endTime) {
        int m = grid.length, n = grid[0].length;
        vis[m - 1][n - 1] = endTime;
        var q = new ArrayList<int[]>();
        q.add(new int[]{m - 1, n - 1});
        for (int t = endTime - 1; !q.isEmpty(); --t) {
            var tmp = q;
            q = new ArrayList<>();
            for (var p : tmp) {
                int i = p[0], j = p[1];
                for (var d : dirs) { // 枚举周围四个格子
                    int x = i + d[0], y = j + d[1];
                    if (0 <= x && x < m && 0 <= y && y < n && vis[x][y] != endTime && grid[x][y] <= t) {
                        if (x == 0 && y == 0) return true;
                        vis[x][y] = endTime; // 用二分的值来标记，避免重复创建 vis 数组
                        q.add(new int[]{x, y});
                    }
                }
            }
        }
        return false;
    }
}

cpp 解法, 执行用时: 944 ms, 内存消耗: 240.2 MB, 提交时间: 2023-02-27 14:33:13 

class Solution {
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    int minimumTime(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size();
        if (grid[0][1] > 1 && grid[1][0] > 1) // 无法「等待」
            return -1;

        int vis[m][n]; memset(vis, -1, sizeof(vis));
        auto check = [&](int end_time) -> bool {
            vis[m - 1][n - 1] = end_time;
            vector<pair<int, int>> q = {{m - 1, n - 1}};
            for (int t = end_time - 1; !q.empty(); --t) {
                vector<pair<int, int>> nxt;
                for (auto &[i, j] : q) {
                    for (auto &d : dirs) { // 枚举周围四个格子
                        int x = i + d[0], y = j + d[1];
                        if (0 <= x && x < m && 0 <= y && y < n && vis[x][y] != end_time && grid[x][y] <= t) {
                            if (x == 0 && y == 0) return true;
                            vis[x][y] = end_time; // 用二分的值来标记，避免重复创建 vis 数组
                            nxt.emplace_back(x, y);
                        }
                    }
                }
                q = move(nxt);
            }
            return false;
        };

        int left = max(grid.back().back(), m + n - 2) - 1, right = 1e5 + m + n; // 开区间
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            (check(mid) ? right : left) = mid;
        }
        return right + (right + m + n) % 2;
    }
};

golang 解法, 执行用时: 356 ms, 内存消耗: 8.1 MB, 提交时间: 2023-02-27 14:32:57 

//BFS
type pair struct{ x, y int }
var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func minimumTime(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	if grid[0][1] > 1 && grid[1][0] > 1 { // 无法「等待」
		return -1
	}

	vis := make([][]int, m)
	for i := range vis {
		vis[i] = make([]int, n)
	}
	endTime := sort.Search(1e5+m+n, func(endTime int) bool {
		if endTime < grid[m-1][n-1] || endTime < m+n-2 {
			return false
		}
		vis[m-1][n-1] = endTime
		q := []pair{{m - 1, n - 1}}
		for t := endTime - 1; len(q) > 0; t-- {
			tmp := q
			q = nil
			for _, p := range tmp {
				for _, d := range dirs { // 枚举周围四个格子
					x, y := p.x+d.x, p.y+d.y
					if 0 <= x && x < m && 0 <= y && y < n && vis[x][y] != endTime && grid[x][y] <= t {
						if x == 0 && y == 0 {
							return true
						}
						vis[x][y] = endTime // 用二分的值来标记，避免重复创建 vis 数组
						q = append(q, pair{x, y})
					}
				}
			}
		}
		return false
	})
	return endTime + (endTime+m+n)%2
}

func min(a, b int) int { if a > b { return b }; return a }

golang 解法, 执行用时: 268 ms, 内存消耗: 9.4 MB, 提交时间: 2023-02-27 14:32:05 

var dirs = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func minimumTime(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	if grid[0][1] > 1 && grid[1][0] > 1 { // 无法「等待」
		return -1
	}

	dis := make([][]int, m)
	for i := range dis {
		dis[i] = make([]int, n)
		for j := range dis[i] {
			dis[i][j] = math.MaxInt
		}
	}
	dis[0][0] = 0
	h := &hp{{}}
	for { // 可以等待，就一定可以到达终点
		p := heap.Pop(h).(tuple)
		d, i, j := p.d, p.i, p.j
		if i == m-1 && j == n-1 {
			return d
		}
		for _, q := range dirs { // 枚举周围四个格子
			x, y := i+q.x, j+q.y
			if 0 <= x && x < m && 0 <= y && y < n {
				nd := max(d+1, grid[x][y])
				nd += (nd - x - y) % 2 // nd 必须和 x+y 同奇偶
				if nd < dis[x][y] {
					dis[x][y] = nd // 更新最短路
					heap.Push(h, tuple{nd, x, y})
				}
			}
		}
	}
}

type tuple struct{ d, i, j int }
type hp []tuple
func (h hp) Len() int              { return len(h) }
func (h hp) Less(i, j int) bool    { return h[i].d < h[j].d }
func (h hp) Swap(i, j int)         { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{})   { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() (v interface{}) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }
func max(a, b int) int { if a < b { return b }; return a }

cpp 解法, 执行用时: 388 ms, 内存消耗: 45.5 MB, 提交时间: 2023-02-27 14:31:49 

class Solution {
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    int minimumTime(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size();
        if (grid[0][1] > 1 && grid[1][0] > 1) // 无法「等待」
            return -1;

        int dis[m][n];
        memset(dis, 0x3f, sizeof(dis));
        dis[0][0] = 0;
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
        pq.emplace(0, 0, 0);
        for (;;) {
            auto[d, i, j] = pq.top();
            pq.pop();
            if (i == m - 1 && j == n - 1)
                return d;
            for (auto &q : dirs) { // 枚举周围四个格子
                int x = i + q[0], y = j + q[1];
                if (0 <= x && x < m && 0 <= y && y < n) {
                    int nd = max(d + 1, grid[x][y]);
                    nd += (nd - x - y) % 2; // nd 必须和 x+y 同奇偶
                    if (nd < dis[x][y]) {
                        dis[x][y] = nd; // 更新最短路
                        pq.emplace(nd, x, y);
                    }
                }
            }
        }
    }
};

java 解法, 执行用时: 140 ms, 内存消耗: 51.6 MB, 提交时间: 2023-02-27 14:31:37 

class Solution {
    private final static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int minimumTime(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid[0][1] > 1 && grid[1][0] > 1) // 无法「等待」
            return -1;

        var dis = new int[m][n];
        for (int i = 0; i < m; ++i)
            Arrays.fill(dis[i], Integer.MAX_VALUE);
        dis[0][0] = 0;
        var pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
        pq.add(new int[]{0, 0, 0});
        for (;;) {
            var p = pq.poll();
            int d = p[0], i = p[1], j = p[2];
            if (i == m - 1 && j == n - 1)
                return d;
            for (var q : dirs) { // 枚举周围四个格子
                int x = i + q[0], y = j + q[1];
                if (0 <= x && x < m && 0 <= y && y < n) {
                    int nd = Math.max(d + 1, grid[x][y]);
                    nd += (nd - x - y) % 2; // nd 必须和 x+y 同奇偶
                    if (nd < dis[x][y]) {
                        dis[x][y] = nd; // 更新最短路
                        pq.add(new int[]{nd, x, y});
                    }
                }
            }
        }
    }
}

python3 解法, 执行用时: 1488 ms, 内存消耗: 29 MB, 提交时间: 2023-02-27 14:31:19 

'''
Dijkstra 算法
'''
class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        if grid[0][1] > 1 and grid[1][0] > 1:  # 无法「等待」
            return -1

        dis = [[inf] * n for _ in range(m)]
        dis[0][0] = 0
        h = [(0, 0, 0)]
        while True:  # 可以等待，就一定可以到达终点
            d, i, j = heappop(h)
            if i == m - 1 and j == n - 1:
                return d
            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 枚举周围四个格子
                if 0 <= x < m and 0 <= y < n:
                    nd = max(d + 1, grid[x][y])
                    nd += (nd - x - y) % 2  # nd 必须和 x+y 同奇偶
                    if nd < dis[x][y]:
                        dis[x][y] = nd  # 更新最短路
                        heappush(h, (nd, x, y))

上一题

© 2024 leetcode.cn