P2120 [第一章例题4.3]Knight Moves
描述
佳佳是一位出色的棋手,声称,除了他之外,没有其他人能如此快速地将骑士从一个位置移动到另一个位置。你能打败他吗?
你的任务是编写一个程序来计算一个骑士从另一个点到达一个点所需的最小移动次数,这样你就有机会比佳佳更快。
对于不熟悉象棋的人来说,骑士可能的移动位置如图所示。
![](https://cdn.maxuetang.cn/ojimages/uploadFiles/image/20180731/20180731154454_400_htimg.jpg)
绿色格子表示可跳到的位置,黑色表示骑士
你的任务是编写一个程序来计算一个骑士从另一个点到达一个点所需的最小移动次数,这样你就有机会比佳佳更快。
对于不熟悉象棋的人来说,骑士可能的移动位置如图所示。
![](https://cdn.maxuetang.cn/ojimages/uploadFiles/image/20180731/20180731154454_400_htimg.jpg)
绿色格子表示可跳到的位置,黑色表示骑士
输入
第一行给出骑士的数量n。对于每一个骑士都有3行,第一行一个整数L,表示棋盘的大小(4≤L≤300),整个棋盘大小为L*L;第二行和第三行分别包含一对整数(x,y),表示骑士的起始点和终点。假设,对于每一个骑士起始点和终点均合理。
输出
对每一个骑士输出一行,个整数表示需要移动的最少步数。如果起始点和终点相同,则输出0。
样例输入
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
样例输出
5 28 0