马的遍历

题目描述

给定 $n \times m$ （ $n,m \le 5$ ）的棋盘和马的起点 $(x,y)$ ，马按中国象棋"日字"移动且不能重复经过同一个格子，求恰好遍历全部 $n\cdot m$ 个格子的路径条数；不存在则输出 $0$ 。第一行整数 $T<10$ 表示测试组数，随后每行四个整数 $n,m,x,y$ （ $0\le x<n,\,0\le y<m$ ）；每组一行输出。

样例：输入 5 4 0 0 输出 32。

思路

$n\cdot m\le 25$ 直接深度优先回溯：从起点出发，每步只在"当前格的合法日字落点"里挑未访问的格子走，用整型位图记录已访问集合；走到无剩余格子时计 $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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#!/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 00:26
# update_at: 2026-09-30 00:26

import sys
from functools import cache

MOVES = ((1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1))  # 马走日的 8 个日字方向


@cache
def neighbors(n: int, m: int) -> tuple[tuple[int, ...], ...]:
    """nbrs[pos]：n×m 棋盘上马从编号 pos 的格子一步可达的格子编号表（越界已滤掉）。

    起点不同但棋盘相同时多组数据可复用同一张表，所以按 (n, m) 做缓存。
    """
    return tuple(
        tuple(
            (r + dr) * m + (c + dc)
            for dr, dc in MOVES
            if 0 <= r + dr < n and 0 <= c + dc < m
        )
        for r in range(n) for c in range(m)
    )


def count_tours(n: int, m: int, x: int, y: int) -> int:
    """统计从 (x, y) 出发、马走日且不重访任何格子的棋盘全遍历路径条数。

    棋盘压成位图：格子 (r, c) 编号为 r*m+c，visited 第 pos 位为 1 表示已访问。
    """
    nbrs = neighbors(n, m)
    total = n * m

    def dfs(pos: int, visited: int, left: int) -> int:
        """从 pos 出发、还有 left 个格子未访问时的完整遍历条数。"""
        if left == 0:
            return 1                                   # 所有格子恰好各走一次
        cnt = 0
        for nxt in nbrs[pos]:
            free = not visited >> nxt & 1              # 移位后取位：目标格还没走过
            if free:
                cnt += dfs(nxt, visited | 1 << nxt, left - 1)
        return cnt

    start = x * m + y
    return dfs(start, 1 << start, total - 1)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        n, m, x, y = next(data), next(data), next(data), next(data)
        out.append(str(count_tours(n, m, x, y)))

    print('\n'.join(out))


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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91/**
 * 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 05:50
 * update_at: 2026-10-05 05:50
 */

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

// 马走日的 8 个日字方向：(dr, dc) 表示行列偏移
const int DR[8] = { 1, 1, -1, -1, 2, 2, -2, -2 };
const int DC[8] = { 2, -2, 2, -2, 1, -1, 1, -1 };

// n <= 5, m <= 5
const int MAXN = 6;
const int MAXM = 6;
const int MAXK = 8;

// nbrs[r][c][k] 表示从 (r,c) 出发的第 k 个合法落点编号（编号 = r*m+c）；k_cnt[r][c] 是合法落点数
int nbrs[MAXN][MAXM][MAXK];
int k_cnt[MAXN][MAXM];

int n, m;
int total_cells;   // n*m
int visited;       // 已访问位图：第 pos 位为 1 表示该格子已访问
ll ans;            // 当前棋盘 + 起点下的全遍历路径条数

// dfs(pos, left)：从 pos 出发、还有 left 个格子未访问时的完整遍历条数。
// visited 进入时已置位 pos，退出前清位实现手工回溯。
void dfs(int pos, int left) {
    if (left == 0) {
        ans++;              // 所有格子恰好各走一次，计一条完整路径
        return;
    }
    int r = pos / m;
    int c = pos % m;
    for (int i = 0; i < k_cnt[r][c]; i++) {
        int nxt = nbrs[r][c][i];
        if ( (visited >> nxt & 1) == 0 ) {     // 落点未访问过
            visited |= 1 << nxt;                // 进入：置位
            dfs(nxt, left - 1);
            visited &= ~(1 << nxt);             // 回溯：清位
        }
    }
}

void build_neighbors() {
    // 预建邻接表：nbrs[r][c] 列出 (r,c) 一步可达的合法落点编号
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            int cnt = 0;
            for (int k = 0; k < 8; k++) {
                int nr = r + DR[k];
                int nc = c + DC[k];
                if (0 <= nr && nr < n && 0 <= nc && nc < m) {
                    nbrs[r][c][cnt++] = nr * m + nc;
                }
            }
            k_cnt[r][c] = cnt;
        }
    }
}

void solve_one(int x, int y) {
    build_neighbors();
    int start_pos = x * m + y;
    visited = 1 << start_pos;
    ans = 0;
    dfs(start_pos, total_cells - 1);
    cout << ans << "\n";
}

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

    int T;
    if ( !(cin >> T) ) return 0;
    while (T--) {
        int x, y;
        cin >> n >> m >> x >> y;
        total_cells = n * m;
        solve_one(x, y);
    }
    return 0;
}

目录

题目描述

思路

参考代码