Vanya and Treasure

题意翻译

题意：给一个n*m的图，每个位置有一个1到p的数字（只有一个p，其他数字可以很多），且每个位置有一把锁，每个数字的锁有打开当前数字+1的钥匙。起点为（1，1），数字为1的格子都是解锁的，问走到数字p最少走多少步。一个点到另外一个点的距离为abs(x2-x1)+abs(y2-y1)。

题目描述

Vanya is in the palace that can be represented as a grid $ n×m $ . Each room contains a single chest, an the room located in the $ i $ -th row and $ j $ -th columns contains the chest of type $ a_{ij} $ . Each chest of type $ x<=p-1 $ contains a key that can open any chest of type $ x+1 $ , and all chests of type $ 1 $ are not locked. There is exactly one chest of type $ p $ and it contains a treasure. Vanya starts in cell $ (1,1) $ (top left corner). What is the minimum total distance Vanya has to walk in order to get the treasure? Consider the distance between cell $ (r_{1},c_{1}) $ (the cell in the row $ r_{1} $ and column $ c_{1} $ ) and $ (r_{2},c_{2}) $ is equal to $ |r_{1}-r_{2}|+|c_{1}-c_{2}| $ .

输入输出格式

输入格式

The first line of the input contains three integers $ n $ , $ m $ and $ p $ ( $ 1<=n,m<=300,1<=p<=n·m $ ) — the number of rows and columns in the table representing the palace and the number of different types of the chests, respectively. Each of the following $ n $ lines contains $ m $ integers $ a_{ij} $ ( $ 1<=a_{ij}<=p $ ) — the types of the chests in corresponding rooms. It's guaranteed that for each $ x $ from $ 1 $ to $ p $ there is at least one chest of this type (that is, there exists a pair of $ r $ and $ c $ , such that $ a_{rc}=x $ ). Also, it's guaranteed that there is exactly one chest of type $ p $ .

输出格式

Print one integer — the minimum possible total distance Vanya has to walk in order to get the treasure from the chest of type $ 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