4964：机器虫洞
文件提交：无需freopen
内存限制：256 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：0
解决：0
题目描述
# 题目描述
一觉醒来，小 Z 发现自己的机器人不见了！经过一顿花里胡哨的操作，小 Z 找到了机器人在哪——机器人被传送到了一个二维空间！
小 Z 发现这个二维空间可以看作是一个 $n * m$ 的地图，机器人一开始处于坐标 $(x_1,y_1)$ 处，而只要小 Z 到达 $(x_2,y_2)$ 坐标处，小 Z 就可以通过技术手段把机器人救回来。
但是在小 Z 尝试向机器人下达移动命令时才发现，这个二维空间居然是由 **虫洞** 组成的。每个坐标 $(i,j)$ 都有一个虫洞，可以用 $a_{i,j}$ 表述虫洞编号。而经过不断的测试，小 Z 发现有些虫洞之间是互相连通的，小 Z 将这些可以互相连通的虫洞用同一个编号来表示，也就是说小 Z 只要进入某个编号为 $x$ 的虫洞，它可以从任意编号为 $x$ 虫洞的坐标离开虫洞。
当然，小 Z 发现机器人的动力是足够脱离虫洞的引力的，它也可以耗费电量来让自己在相邻的坐标位置之间直接进行移动，每次移动到 **上下左右** 四个方向的位置，需要花费一格电量。但是由于虫洞存在吸引力，小 Z 发现每次进入虫洞都会导致机器人受损，经过测量，机器人最多还能进入 $k$ 次虫洞，之后如果再次进入虫洞就会导致机器人损坏。
为了设计一套救援方案，顺便还能收集一下二维空间的信息。小 Z 想知道，在机器人不损坏的情况下，机器人移动到 $(x2,y2)$ 坐标处最少需要花费多少电量？
## 输入格式
从 `hole.in` 文件读入数据。
输入第一行是两个整数 $n,m,k$，含义如题。
输入第二行包含四个整数 $x_1,y_1,x_2,y_2$。
接下来 $n$ 行，每行 $m$ 个数字，分别表示每个坐标对应的虫洞编号。
## 输出格式
输出到 `hole.out` 文件。
输出一个整数，表示机器人最少花费的电量。
## 样例
### 输入样例
```
5 5 2
1 1 5 5
1 1 2 2 2
2 3 3 3 3
4 4 5 5 6
7 4 7 8 8
8 9 9 9 9
```
### 输出样例
```
3
```
## 说明/提示
### 样例解释
其中一种方案为：
1. $(1,1) \rightarrow (2,1)$，花费 $1$ 电量
2. $(2,1) \rightarrow (3,1)$，花费 $1$ 电量
3. $(3,1) \rightarrow (4,2)$，使用虫洞移动
4. $(4,2) \rightarrow (5,2)$，花费 $1$ 电量
5. $(5,2) \rightarrow (5,5)$，使用虫洞移动
最小花费为 $3$ 电量
### 数据范围
| 数据点编号 | $n,m$ | $k$ | 虫洞编号 |
| :--------: | :-------------------: | :-------------: | :---------: |
| $1$ | $1 \le n, m \le 10$ | $k = 0$ | $[1, 100]$ |
| $2$ | $1 \le n, m \le 10$ | $k = 1$ | $[1, 100]$ |
| $3 \sim 5$ | $1 \le n, m \le 10$ | $k = 2$ | $[1, 100]$ |
| $6 \sim 9$ | $1 \le n, m \le 1000$ | $k = 2$ | $[1, 1000]$ |
| $10 \sim 20$| $1 \le n, m \le 1000$ | $1 \le k \le 5$ | $[1, 1000]$ |