3925: 张老师的机器虫洞

内存限制：256 MB 时间限制：2.000 S
评测方式：文本比较 命题人：
提交：0 解决：0

题目描述

一觉醒来，张老师发现自己的机器人不见了！

经过一顿花里胡哨的操作，徐张老师找到了机器人在哪——机器人被传送到了一个二维空间！

张老师发现这个二维空间可以看作是是一个 $n * m$ 的地图，机器人一开始处于坐标 $(x_1,y_1)$ 处，而只要张老师到达 $(x_2,y_2)$ 坐标处，张老师就可以通过技术手段把机器人救回来

但是在张老师尝试向机器人下达移动命令时才发现，这个二维空间居然是由 **虫洞** 组成的

每个坐标都有一个虫洞，而经过不断的测试，张老师发现有些虫洞之间是互相连通的，张老师将这些可以互相连通的虫洞用同一个编号来表示，也就是说张老师只要进入某个编号为 $i$ 的虫洞，它可以从任意编号为 $i$ 虫洞的坐标离开虫洞

当然，张老师发现机器人的动力是足够脱离虫洞的引力的，它也可以耗费电量来让自己在相邻的坐标位置之间直接进行移动，每次移动到 **上下左右** 四个方向的位置，需要花费一格电量

但是由于虫洞存在吸引力，张老师发现每次进入虫洞都会导致机器人受损，经过测量，机器人最多还能进入 $k$ 次虫洞，之后如果再次进入虫洞就会导致机器人损坏

为了设计一套救援方案，顺便还能收集一下二维空间的信息

张老师想知道，在机器人不损坏的情况下，机器人移动到 $(x2,y2)$ 坐标处最少需要花费多少电量？

输入

输入第一行是两个整数 $n,m,k$,含义如题

输入第二行包含四个整数 $x_1,y_1,x_2,y_2$

接下来 $n$ 行，每行 $m$ 个数字，分别表示每个坐标对应的虫洞编号
| 数据点编号 | $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]$ |

输出

输出一个整数，表示机器人最少花费的电量

样例输入 复制 

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,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$ 电量 

来源/分类

提交提交记录统计露一手!