# 1970. 你能穿过矩阵的最后一天
### 题目地址(1970. 你能穿过矩阵的最后一天)
### 题目描述
```
给你一个下标从 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. 最小体力消耗路径](/leetcode-solution/medium/1631.path-with-minimum-effort.md) 类似。
由于：
* 如果第 n 天可以，那么小于 n 天都可以到达最后一行
* 如果第 n 天不可以，那么大于 n 天都无法到达最后一行
这有很强的二段性。基于此，我们可以想到使用能力检测二分中的**最右二分**。而这里的能力检测，我们可以使用 DFS 或者 BFS。而由于起点可能有多个（第一行的所有陆地），因此使用**多源 BFS** 复杂度会更好，因此我们这里选择 BFS 来做。
本题还有一种并查集的解法，也非常有意思。具体可参考力扣中国的[官方题解](https://leetcode-cn.com/problems/last-day-where-you-can-still-cross/solution/ni-neng-chuan-guo-ju-zhen-de-zui-hou-yi-9j20y/) 的方法二。
### 代码
* 语言支持：Python3
Python3 Code:
```python
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)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1970.last-day-where-you-can-still-cross.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.