地下探险
题号：NC308032
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一位勇敢的探险家正准备深入一个神秘的地下洞穴，寻找传说中的古代遗物。
整个洞穴系统可以看作一个二维网格。
探险家每次只能向上、下、左、右四个方向移动一格。

探险家携带的氧气瓶是有限的，最多只够支持连续行走 k 步。
氧气耗尽后，必须立刻找到洞穴内的氧气补给站来补充氧气，否则将无法继续前进。
在补给站，氧气可以被瞬间充满，恢复到最大值（即可再次行走 k 步）。

您的任务是编写一个程序，计算探险家从洞穴入口到达古代遗物所在位置所需的最短路径长度（总步数）。

输入描述:

输入包含以下部分：

1.  第一行 : 洞穴的尺寸，包含两个整数 m 和 n，分别代表网格的行数和列数。
1 \le m, n \le 1000

2. 接下来的 m 行 : 每行包含 n 个整数，描述了 m \times n 的洞穴网格。每个整数的含义如下：
0 : 可通行的洞穴路径。
1 : 无法通行的岩壁障碍。
2 : 氧气补给站。

3. 倒数第三行 : 两个整数 r_s, c_s，代表探险家出发的入口坐标（左上角为 (0,0)）。

4. 倒数第二行 : 两个整数 r_d, c_d，代表古代遗物所在的终点坐标。

5. 最后一行 : 一个整数 k，代表氧气瓶支持的最大连续移动步数。
1 \le k \le 100000

输出描述:

输出一个整数，表示从入口到遗物所在地的最短路径长度。如果无法到达，则输出 -1 。
示例1

输入

复制 
3 3
0 0 0
0 2 0
0 0 0
0 0
2 2
2

输出

复制 
4
示例2

输入

复制 
3 3
0 0 0
1 1 1
0 0 0
0 0
2 2
2

输出

复制 
-1

备注:

本题由牛友@Charles 整理上传