解题思路

当时间为 $t$ 时，所有高度 $\le t$ 的格子都可视为可通行。要求从 $(0,0)$ 到 $(n-1,n-1)$ 的最小 $t$，使得存在一条路径，其上所有格子的高度最大值最小。

有三种常见做法（任取其一即可 AC）：

1. 最短路（Dijkstra，最小化路径上的最大值） 将每个格子视为节点，边权为到达相邻格子的“代价”。对一条路径，其“代价”定义为路径上格子高度的最大值。Dijkstra 的写法是：

• 堆中状态为 $(\text{cost}, x, y)$，其中 $\text{cost}$ 表示从起点到 $(x,y)$ 的路径上出现的最大高度。

题目内容

在偏远山区有一片$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