1835: [NewOJ Week 9] 跳房子游戏

内存限制:512 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:29 通过:2

题目描述

给你一个N*N个单位的方形地板,每个单位上有一个1-K的数字。
跳房子游戏需要从编号为1开始,依次跳到编号为2、3、4、...、K的格子。
坐标(x1,y1)和(x2,y2)之间的距离定义为:min((x1-x2)^2, (y1-y2)^2)。
请求出跳房子游戏完成游戏的最短路径。

输入格式

输入第一行为正整数N和K,1≤N≤500,1≤K≤N*N
接下来N行,每行N个数字,表示给定的地板,每个单位上的数字1x≤K。

输出格式

如果不存在这样的路径,输出-1,否则输出最短路径。

输入样例 复制

样例1:
10 5
5 1 3 4 2 4 2 1 2 1
4 5 3 4 1 5 3 1 1 4
4 2 4 1 5 4 5 2 4 1
5 2 1 5 5 3 5 2 3 2
5 5 2 3 2 3 1 5 5 5
3 4 2 4 2 2 4 4 2 3
1 5 1 1 2 5 4 1 5 3
2 2 4 1 2 5 1 4 3 5
5 3 2 1 4 3 5 2 3 1
3 4 2 5 2 5 3 4 4 2

样例2:
10 30
18 13 30 15 18 16 14 1 5 5
17 18 7 30 14 30 13 14 1 28
28 24 7 23 9 10 5 12 21 6
11 16 6 2 27 14 1 26 7 21
16 2 9 26 6 24 22 12 8 16
17 28 29 19 4 6 21 19 6 22
11 27 11 26 13 23 10 3 18 6
14 19 9 8 17 6 16 22 24 1
12 19 10 21 1 8 20 24 29 21
21 29 1 23 23 24 6 20 25 17

输出样例 复制

样例1:
0

样例2:
19