← 返回题目列表

Codeforces · 677/D

D. 万尼亚和宝藏

中文机器翻译题面 查看原题

Vanya 所在的宫殿可以表示为 n × m 的网格。每个房间包含一个箱子,位于第​​ i 行第 j 列的房间包含 aij 类型的箱子。每个 x ≤ p - 1 类型的箱子都包含一把钥匙,可以打开任何 x + 1 类型的箱子,并且所有类型 1 的箱子都没有上锁。 p型箱子只有一个,里面有宝藏。

Vanya 从单元格 (1, 1)(左上角)开始。为了得到宝藏,Vanya 必须步行的最短总距离是多少?考虑单元格 (r1, c1)(r1 行和 c1 列中的单元格)和 (r2, c2) 之间的距离等于 |r1 - r2| + |c1 - c2|。

输入

输入的第一行包含三个整数 n、m 和 p (1 ≤ n, m ≤ 300, 1 ≤ p ≤ n·m)——分别代表宫殿的行数和列数以及不同类型箱子的数量。

以下 n 行每行包含 m 个整数 aij (1 ≤ aij ≤ p)——对应房间中箱子的类型。保证对于从1到p的每个x,至少有一个这种类型的箱子(即,存在一对r和c,使得arc = x)。另外,还保证只有一个 p 类型的箱子。

输出

打印一个整数 - Vanya 为了从 p 类型的箱子中取出宝藏而必须行走的最小可能总距离。

示例

输入 #1

3 4 3
2 1 1 1
1 1 1 1
2 1 1 3

输出 #1

5

输入 #2

3 3 9
1 3 5
8 9 7
4 6 2

输出 #2

22

输入 #3

3 4 12
1 2 3 4
8 7 6 5
9 10 11 12

输出 #3

11