首页 > 试题广场 >

象棋马走步问题

[编程题]象棋马走步问题

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在一个 ${8 \times 8}$ 的象棋棋盘上，每个格子被依次标号为 0 - 63。
有一个棋子按照马的走法（即“日”字形）移动。棋盘中存在一些障碍物，需要输入障碍物的相关信息以及棋子的初始位置和最终位置。
棋子移动时不能超出棋盘边界，也不能碰到障碍物。要求找出棋子从初始位置到达最终位置的最短路径，并输出路径中经过的格子标号。如果存在多条最短路径，每多输出一条额外的最短路径可额外加分，总分不超过 100 分。
若无法从初始位置到达最终位置，则输出 "UNREACHED"。

输入描述:

第一行输入一个整数 ，表示障碍物的个数。
第二行输入  个整数，代表障碍物所在的格子标号。
第三行输入两个整数，第一个整数为棋子的初始位置标号，第二个整数为最终位置标号。
，障碍物位置和棋子位置均为 [0, 63] 内的整数。

输出描述:

若存在从初始位置到最终位置的最短路径，输出路径中经过的格子标号，标号之间用空格分隔。
若有多条最短路径，可依次输出多条路径，每条路径占一行。 按照数的大小排序。
若无法到达最终位置，输出 "UNREACHED"。

示例1

输入

10
10 20 30 40 50 60 27 32 34 26
0 63

输出

0 17 2 12 29 46 63
0 17 2 19 29 46 63
0 17 2 19 36 46 63
0 17 2 19 36 53 63
0 17 11 21 31 46 63
0 17 11 21 36 46 63
0 17 11 21 36 53 63
0 17 11 21 38 53 63
0 17 11 28 38 53 63
0 17 11 28 43 53 63

算法知识视频讲解