POJ 1915 Knight Moves

题目描述

给定一个大小为 $l \times l$ 的国际象棋棋盘，计算骑士从一个起点移动到目标点所需的最少步数。

骑士走法为国际象棋标准“日”字走法，共有 8 个移动方向：

输入格式

• 第一行一个整数 $n$，表示测试用例组数。
• 每组测试用例包含三行：
  1. 一个整数 $l$，表示棋盘边长，满足 $4 \le l \le 300$。
  2. 两个整数，表示骑士的起点坐标。
  3. 两个整数，表示骑士的终点坐标。
• 坐标范围：$0 \le x, y < l$，数据保证坐标合法。

输出格式

对每组数据，输出从起点到终点的最少步数。 若起点与终点相同，输出 $0$。

样例输入

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

样例输出

5
28
0

数据范围

对于 $100\%$ 的数据，有 $4\le L\le 300$，保证 $0\le x,y\le L-1$。