【例8.3】最少步数

题目描述

在 100×100 的棋盘上，一匹马既能走“日”字也能走“田”字。输入两个起点 A、B 的坐标，输出它们到左上角 (1,1) 的最少步数。

思路

12 种走法都成对取反，图是无向无权图，所以从 (1,1) 反向做一次 BFS 即可得到所有格子到 (1,1) 的最短距离；两个起点各查一次表即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 05:33
# update_at: 2026-09-30 05:44

import sys
from collections import deque

BOARD = 100  # 棋盘 100×100，走法在两个轴上独立地取增量，正好写成 (行, 列) 两维
POINTS = 2   # 输入是黑马、白马两行坐标，两匹马的终点都是 (1, 1)

MOVES = tuple(  # 12 种走法：日字的 8 个 L 型，加上田字的 4 个对角
    [(dr * a, dc * b) for dr, dc in ((1, 2), (2, 1)) for a in (-1, 1) for b in (-1, 1)]  # 8
    + [(2 * a, 2 * b) for a in (-1, 1) for b in (-1, 1)]  # 4
)


def corner_distances() -> dict[tuple[int, int], int]:
    """棋盘上每个格子到 (1, 1) 的最少步数。

    两匹马都在 (1, 1) 收尾，所以从 (1, 1) 出发做一次 BFS，整张距离表两问共用。
    走法是 (行增量, 列增量) 的定长组合，且集合关于取负封闭（能走过去就能走回来），
    因此反向搜索得到的距离与正向完全一致。
    """
    dist = {(1, 1): 0}
    q = deque(dist)
    while q:
        point = q.popleft()
        for dr, dc in MOVES:
            nxt = (point[0] + dr, point[1] + dc)
            inside = 1 <= nxt[0] <= BOARD and 1 <= nxt[1] <= BOARD
            if inside and nxt not in dist:  # BFS 首次访问即最短路
                dist[nxt] = dist[point] + 1
                q.append(nxt)
    return dist


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    dist = corner_distances()
    # 输入就是两行坐标，黑马、白马各查一次表（同一个生成器按顺序取四个数）
    print('\n'.join(str(dist[(next(data), next(data))]) for _ in range(POINTS)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 10:02
 * update_at: 2026-10-05 10:02
 */
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef long long ll;

const int N = 105;
const int MOVES = 12;

// dr, dc: 12 种马步，前 8 种是日字，后 4 种是田字
int dr[MOVES] = {-1, -1, 1, 1, -2, -2, 2, 2, -2, -2, 2, 2};
int dc[MOVES] = {-2, 2, -2, 2, -1, 1, -1, 1, -2, 2, -2, 2};

int dist[N][N]; // dist[r][c] 表示 (r,c) 到 (1,1) 的最少步数

struct Node {
    int r;
    int c;
};

queue<Node> q;

// 从 (1,1) 反向 BFS，建立全图距离表
void bfs() {
    memset(dist, -1, sizeof(dist));
    dist[1][1] = 0;
    q.push((Node){1, 1});
    while (!q.empty()) {
        Node u = q.front();
        q.pop();
        for (int k = 0; k < MOVES; k++) {
            int nr = u.r + dr[k];
            int nc = u.c + dc[k];
            if (nr < 1 || nr > 100 || nc < 1 || nc > 100) continue;
            if (dist[nr][nc] != -1) continue;
            dist[nr][nc] = dist[u.r][u.c] + 1;
            q.push((Node){nr, nc});
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    bfs();

    int ar, ac, br, bc;
    cin >> ar >> ac;
    cin >> br >> bc;
    cout << dist[ar][ac] << "\n";
    cout << dist[br][bc] << "\n";

    return 0;
}