A93900.Alice的奇妙爬山之旅

在一个 $n\times m$ 的网格上，每个格子要么是障碍，要么是可通行并附有一个高度 $h_{i,j}$。你从起点 $S$ 走到终点 $T$。

• 每一步只能向上下左右 $4$ 个方向移动；
• 只能在网格内且非障碍的格子间移动。

当你从格子 $u$ 移动到相邻格子 $v$ 时，这条边的难度定义为

$$\mathrm{diff}(u,v)=\lvert h_u-h_v\rvert.$$

你有 $K$ 次硬跨机会：最多选择 $K$ 条经过的边，将这几条边的难度视为 $0$。你的目标是使整条路径上最大的一条边难度尽可能小。

请输出在最优策略下，路径上“最大边难度”的最小可能值。
若 $S$ 无法到达 $T$（被障碍隔开），输出 $-1$。

第一行包含三个整数 $n,m,K$。
接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示障碍网格：# 表示障碍、. 表示可通行。
再接下来 $n$ 行，每行包含 $m$ 个整数，表示高度 $h_{i,j}$（对障碍格给出的高度忽略）。
最后一行包含四个整数 $sx,sy,tx,ty$，表示起点 $(sx,sy)$ 与终点 $(tx,ty)$ 的行列坐标（均为 $1$ 下标）。
保证：$(sx,sy)$ 与 $(tx,ty)$ 均为可通行格（对应为 .）。

输出一个整数，表示最小化后的最大边难度。若 $S$ 无法到达 $T$，输出 $-1$。

测试点	$n\times m$	$K$ 范围	$H_{ij}$
$1\sim 3$	$300\times 300 \sim 600\times 600$	$1\sim n\cdot m$	$-10^8 \le H_{ij} \le 10^8$
$4\sim 5$	$400\times 400 \sim 800\times 800$	$1\sim n\cdot m$	$-10^8 \le H_{ij} \le 10^8$
$6\sim 20$	$600\times 800 \sim 1000\times 1000$	$1\sim n\cdot m$	$-10^8 \le H_{ij} \le 10^8$