Skip to content

Latest commit

 

History

History
127 lines (82 loc) · 4.55 KB

1970.last-day-where-you-can-still-cross.md

File metadata and controls

127 lines (82 loc) · 4.55 KB

题目地址(1970. 你能穿过矩阵的最后一天)

https://leetcode-cn.com/problems/last-day-where-you-can-still-cross/

题目描述

给你一个下标从 1 开始的二进制矩阵,其中 0 表示陆地,1 表示水域。同时给你 row 和 col 分别表示矩阵中行和列的数目。

一开始在第 0 天,整个 矩阵都是 陆地 。但每一天都会有一块新陆地被 水 淹没变成水域。给你一个下标从 1 开始的二维数组 cells ,其中 cells[i] = [ri, ci] 表示在第 i 天,第 ri 行 ci 列(下标都是从 1 开始)的陆地会变成 水域 (也就是 0 变成 1 )。

你想知道从矩阵最 上面 一行走到最 下面 一行,且只经过陆地格子的 最后一天 是哪一天。你可以从最上面一行的 任意 格子出发,到达最下面一行的 任意 格子。你只能沿着 四个 基本方向移动(也就是上下左右)。

请返回只经过陆地格子能从最 上面 一行走到最 下面 一行的 最后一天 。

 

示例 1:

输入:row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
输出:2
解释:上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 2 天。


示例 2:

输入:row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
输出:1
解释:上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 1 天。


示例 3:

输入:row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
输出:3
解释:上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 3 天。


 

提示:

2 <= row, col <= 2 * 104
4 <= row * col <= 2 * 104
cells.length == row * col
1 <= ri <= row
1 <= ci <= col
cells 中的所有格子坐标都是 唯一 的。

前置知识

  • 多源 BFS
  • 二分

公司

  • 暂无

思路

本题和 1631. 最小体力消耗路径 类似。

由于:

  • 如果第 n 天可以,那么小于 n 天都可以到达最后一行
  • 如果第 n 天不可以,那么大于 n 天都无法到达最后一行

这有很强的二段性。基于此,我们可以想到使用能力检测二分中的最右二分。而这里的能力检测,我们可以使用 DFS 或者 BFS。而由于起点可能有多个(第一行的所有陆地),因此使用多源 BFS 复杂度会更好,因此我们这里选择 BFS 来做。

本题还有一种并查集的解法,也非常有意思。具体可参考力扣中国的官方题解 的方法二。

代码

  • 语言支持:Python3

Python3 Code:

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        def can(d):
            visited = set()
            q = collections.deque([(0,j) for j in range(col)])
            for x, y in cells[:d]:
                visited.add((x-1, y-1))
            while q:
                x,y = q.popleft()
                if (x,y) in visited: continue
                visited.add((x,y))
                if x == row - 1: return True
                for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
                    if 0 <= x + dx < row and 0 <= y + dy < col: q.append((x+dx, y+dy))
            return False

        l, r = 0, row * col
        while l <=r :
            mid = (l+r)//2
            if can(mid):
                l = mid + 1
            else:
                r = mid - 1
        return r

复杂度分析

令 n 为 row 和 col 的乘积。

  • 时间复杂度:$O(nlogn)$
  • 空间复杂度:$O(n)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。