问题 1271. -- 珂朵莉、威廉和第十一兽 (a.k.a Chtholly, Williem and Croyance)

1271: 珂朵莉、威廉和第十一兽 (a.k.a Chtholly, Williem and Croyance)

时间限制: 1 Sec  内存限制: 128 MB
提交: 34  解决: 9
[提交][状态][讨论版]

题目描述

珂朵莉在 68 号悬浮岛休息的时候,突然感到了“第十一兽”的气息...

她感觉到第十一兽将会在第 28 号岛——威廉的家降落!

拯救威廉,刻不容缓!

但是,她发现:在 68 号悬浮岛与第 28 号悬浮岛之间,有一个神奇的迷宫!

在这个迷宫里,有 type 种不同的东西,必须按照 1, 2, 3, ..., type, 1, 2, 3, .... 的顺序走,即收集到第 i 种东西所在的位置以后只能到相邻的含有第 i mod type + 1 的东西的位置,到达终点以后即可停止收集。否则就会因为兽的力量而死亡!

帮帮珂朵莉吧!

输入

多组输入到 EOF 结束,对于每组数据:

第一行 n, m, type,分别表示 n * m 的迷宫需要搜集 type 种东西。

以下 n 行,每一个字符 [0, type] ,描述了这个迷宫。0 代表不可达,pij = 1,2, ..., type 表示这个点有 pij类型的东西。

接下来一行,描述 fx, fy, tx, ty,描述了 珂朵莉 和 威廉 的位置 。

注意, 我们需要以坐标为 (fx, fy) 的物品开始收集。

起点和终点的对应值可能是 0。

输出

一个数字,表示珂朵莉需要走多少步。

如果不能到达,输出 "-1" (不含引号)。

样例输入

3 3 3
123
231
312
1 1 2 2
3 3 3
123
230
312
1 1 3 3

样例输出

2
4

提示


对于第一个样例,从 (1, 1) -> (1, 2) -> (2, 2) 即可到达;
对于第二个样例,从 (1, 1) -> (1, 2) -> (2, 2) -> (3, 2) -> (3, 3) 即可到达。
n, m <= 100; type <= 9

来源

[提交][状态][讨论版]