中国象棋里面的马已经被证明可以走向任何的位置,如果给定一个坐标,需要设计一个算法,找出马到达这个坐标最短的路径,并输出中间的坐标。
马的走法是“日”字形,即如果某一步的坐标是[x,y],则下一步坐标是[x±1,y±2]或[x±2,y±1]。
- 马的初始位置在[1,0]。
- 输入:两个数字,分成两行,目标坐标 x,目标坐标 y
- 查询输入及要求的输出:最少步数数字,接下来每一行输出中间途径坐标,每行两个数,先x 后 y,空格隔开。直到输入-1 作为结尾,程序退出。
注意:
- 路径需要包括终止节点,但是不能包括起始节点(即不要输出 1 0 这个位置)。
7
3
3
1
4
1
1
1
5
7
3
7
8
4
1
5
5
4
1
7
4
6
6
0
-1
- 输出
3
3 1
5 2
7 3
1
3 1
2
2 2
4 1
3
0 2
2 3
1 1
5
0 2
1 4
2 6
3 8
5 7
5
0 2
1 4
0 6
1 8
3 7
5
0 2
2 3
4 4
6 5
8 4
3
0 2
2 3
1 5
4
0 2
1 4
3 5
5 4
5
0 2
1 4
0 6
2 5
1 7
3
2 2
3 4
4 6
3
2 2
4 1
6 0