2368. 最小步数
1000ms
256MB
简单
广度优先搜索
BFS
题目描述
在一个大小为 $100 \times 100$ 的网格地图中，起点固定为 $(1, 1)$。现在给定两个目标点 $A$ 和 $B$ 的坐标。
按照国际象棋中“马走日”的规则（即每次移动横向跨越 1 个单位且纵向跨越 2 个单位，或者横向跨越 2 个单位且纵向跨越 1 个单位，共有 8 种可能的移动方向），求从起点分别移动到 $A$ 点和 $B$ 点的最少步数。
数据保证起点一定可以到达 $A$ 点和 $B$ 点。
输入格式
- 第一行包含两个正整数 $x_A$ 和 $y_A$，表示目标点 $A$ 的坐标。
- 第二行包含两个正整数 $x_B$ 和 $y_B$，表示目标点 $B$ 的坐标。
输出格式
- 第一行输出一个整数，表示到目标点 $A$ 的最少步数。
- 第二行输出一个整数，表示到目标点 $B$ 的最少步数。
样例 1
输入 (Input)
12 16 18 10
输出 (Output)
10 10
样例 2
输入 (Input)
2 3 4 1
输出 (Output)
1 3
- 地图大小固定为 $100 \times 100$。
- 所有坐标值均在 $[1, 100]$ 之间。
- **算法提示**：
由于棋盘大小只有 $100 \times 100$，且起点固定为 $(1, 1)$，因此最有效率的方案是：
1. 在程序开始时，从 $(1, 1)$ 点启动一次广度优先搜索（BFS），求出到达棋盘上所有格子的最短距离，并保存在二维数组 `dist` 中。
2. 读入 $A$ 和 $B$ 的目标坐标。
3. 直接以 $O(1)$ 的时间复杂度输出 `dist[xa][ya]` 和 `dist[xb][yb]`。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功