解题思路
当时间为 t 时，所有高度 ≤t 的格子都可视为可通行。要求从 (0,0) 到 (n−1,n−1) 的最小 t，使得存在一条路径，其上所有格子的高度最大值最小。
有三种常见做法（任取其一即可 AC）：
- 最短路（Dijkstra，最小化路径上的最大值）
将每个格子视为节点，边权为到达相邻格子的“代价”。对一条路径，其“代价”定义为路径上格子高度的最大值。Dijkstra 的写法是：
P4205.第4题-村落撤离
题目内容
在偏远山区有一片n×n的村落群，每个村落(i,j)都建在海拔为grid[i][j]米的山地上。近期连续暴雨引发山洪，洪水水位以每小时上涨1米的速度淹没村落 一 第t小时时，水位恰好达到t米。
由于洪水来得突然，你需要从位于西北角的起始村落(0,0)出发，尽快赶到位于东南角的安全避难所(n−1,n−1)。已知你可以在相邻的村落间自由移动(上下左右四个方向)，但有一个关键限制:只有当两个村落的海拔都被当前水位淹没时，你才能在它们之间移动(水位需同时覆盖起点和终点村落，否则无法跨越地形差).
假设你在已淹没的区域内移动速度极快(耗时可忽略)，且全程必须待在村落群的边界内。请计算你从起始村落到达安全避难所的最短撤离时间(即最早能出发并成功抵达避难所的小时数t)。
输入描述
第一行输入为N，表示grid的大小。
之后N行输入分别表示grid中村落的海拔
输出描述
输出一个整数，表示最短撤离时间。
补充说明
提示:
- n==grid.length
- n==grid[i].length
- 1<=n<=1000
- 0<=grid[][]<n∗n
- grid[i][j]中每个值均无重复
样例1
输入
2
0 2
1 3
输出
3
说明
可以选择区间[1,3]对应子数组为1,1,1,f和g值都为1，乘积也为1，可以证明不存在更优的答案。
样例2
输入
5
0 1 2 3 4
24 23 22 21 5
12 13 14 15 16
11 17 18 19 20
10 9 8 7 6
输出
16
