Meta VO 面试真题解析：网格洪水最晚连通年份（Maximum Years Until the Start-to-End Path Is Flooded）

Given a grid of land heights. For example:

start
6 5 4 5 5
4 2 5 1 1
5 5 2 1 5
2 3 2 4 4
5 4 5 5 6
end

The upper-left corner is the start cell, and the bottom-right corner is the end cell. You may assume that the start and end cells are of equal height and are the highest points in the grid.

Initially, the water level is 0. Due to global warming, the water level increases by 1 every year. A cell is flooded if the water level is greater than or equal to its height.

How many years do we have before there is no longer a path from the start to the end cell?

Example:

S = start, E = end, X = flooded

In 1 year:

S....
...XX
...X.
.....
....E

In 2 years:

S....
.X.XX
..XX.
X.X..
....E

In 3 years:

S....
.X.XX
..XX.
XXX..
....E

Answer: 3

这道题本质上是在网格中寻找一条从左上角到右下角的“可通行路径”，但随着年份增加，水位每年上升 1，低于或等于当前水位的格子会被淹没。关键不是逐年模拟整张图，而是把问题转化为：一条路径上能够承受的最大水位是多少。只要路径中所有格子的高度都高于当前水位，路径仍然存在；当水位上升到某个临界值后，所有可能路径都会被切断。常见做法是用 BFS/DFS 判断某一年是否还能连通，再结合二分查找答案，或者用并查集 / 最小瓶颈路径思想直接求出“最晚还能连通的年份”。