A6930 | $Alice的奇妙爬山之旅$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

在一个 $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$。

输入 #1

3 4 1
..#.
..#.
....
1 2 3 4
2 3 4 5
3 4 100 6
1 1 3 4

输出 #1

输入 #2

输出 #2

测试点$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$

测试点	$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$

C++ 编辑器

输入

输出