You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在 $n\times m$ 的网格图中，大头兵 u 需要将长官的信件从 $(sx, sy)$ 送到 $(tx, ty)$。每个格子上可能有障碍物，有障碍物的格子用 1 表示，这些格子无法通行，其余格子用 0 表示，没有障碍物的格子可以自由通行。u 每次可以选择上下左右任意方向走一格，上下移动需要穿越河流，移动一次耗时为 $k$ 秒；左右移动是在陆地行进，移动一次耗时 1 秒。

因为某些原因，u 需要保证从 $(sx, sy)$ 到 $(tx, ty)$ 的最短路恰好耗时 $s$ 秒，幸运的是，u 可以任意选择过河交通工具，也就是说过河耗时 $k$ 秒可以由 u 决定。但是 u 只能选择同种类型的过河交通工具，也就是说在这次送信任务中所有的 $k$ 是统一的。

那么合适的 $k$ 是多少呢？

输入格式

第一行两个正整数 $n, m$

第二行四个正整数 $s x, s y, t x, t y$，分别表示送信任务的起点和终点坐标

接下来 $n$ 行，每行 $m$ 个数，描述网格图

最后一行一个正实数 $s$

输出格式

输出仅一行一个实数 $k$，表示答案，四舍五人保留 3 位小数，（评测时开启逐行比较模式，以保证精度）

数据保证有解。如有多解， $k$ 应当尽可能小，最小值为 $0$。

4 4
1 1 4 4
0 0 1 1
1 0 0 0
0 0 1 0
0 0 0 0
5.00

0.667

###附加样例 a.in
a.out

数据范围与提示

对于所有数据，满足 $1 \leq n, m \leq 100,1 \leq s \leq 10^5, 1 \leq s x, t x \leq n, 1 \leq s y, t y \leq m$。

• 特殊性质 A：$n, m \leq 10$，且保证从起点到终点只有一条不重复经过同一个点的路径。