usaco-4.4.1 棋盘游戏

形式化题目

给定长度为 $2N+1$ 的序列，初始下标 $1 \sim N$ 为白棋 $W$ ，下标 $N+1$ 为空格 $\_$ ，下标 $N+2 \sim 2N+1$ 为黑棋 $B$ 。

定义每次操作可将空格 $\_$ 与某位置棋子交换，合法操作为：

相邻平移：空格与相邻棋子交换（距离为 $1$ ）；
跨越跳跃：棋子跳过一个与其异色的棋子到达空格（距离为 $2$ ）。

求将序列变为左侧 $N$ 个 $B$ 、中间空格 $\_$ 、右侧 $N$ 个 $W$ 的最少步数操作序列。输出每一步被移动入空格的原棋子下标（即每次操作后空格所在的绝对位置，从 $1$ 开始计数）。若有多组最少步数解，输出字典序最小的一组解。

正解

思路

1. 理论最少步数推导

考虑目标状态下所有黑棋都位于所有白棋的左侧：

初始状态下，任意一对 $(W, B)$ 中白棋均在黑棋左侧。目标状态下，所有黑棋均在白棋左侧。
共有 $N$ 个白棋与 $N$ 个黑棋，总共构成了 $N \times N = N^2$ 个异色棋子对。
相邻平移：棋子仅移动 1 格入空格，未发生棋子之间的跨越，异色对的相对先后顺序不变。
跨越跳跃：一个棋子跳过一个与其异色的棋子，恰好交换了这一对黑白棋子的相对顺序，使逆序对数加 1。
要使全部 $N^2$ 个异色对完成翻转，必须且恰好需要发生 $N^2$ 次跳跃！

再考察棋子的净位移：

每个白棋最终从左半部分到达右半部分，总净向右位移至少为 $N+1$ 格， $N$ 个白棋总位移至少为 $N(N+1)$ 格；
每个黑棋最终从右半部分到达左半部分，总净向左位移至少为 $N+1$ 格， $N$ 个黑棋总位移至少为 $N(N+1)$ 格；
所有棋子的总移动距离至少为 $2N(N+1) = 2N^2 + 2N$ 格；
每次跳跃贡献 2 格位移，共 $N^2$ 次跳跃贡献 $2N^2$ 格位移；
剩余位移必须全部由相邻平移提供，每次平移贡献 1 格位移，因此平移次数至少为 $2N$ 次。

由此得出，达成目标所需的最少移动步数恒等于：

S = N^2 + 2N = (N+1)^2 - 1

2. 搜索设计与字典序保证

由于步数已被严格确定为 $(N+1)^2 - 1$ ，且为保证无回退和最少步数，棋子遵循单向移动规则：

白棋只能向右移或向右跳（移入左侧的空格）；
黑棋只能向左移或向左跳（移入右侧的空格）。

设当前空格位置为 blank（下标 $0 \sim 2N$ ），合法的移入棋子候选位置为：

blank - 2（白棋右跳）：需满足第 blank - 2 位为白棋且第 blank - 1 位为黑棋；
blank - 1（白棋右移）：需满足第 blank - 1 位为白棋；
blank + 1（黑棋左移）：需满足第 blank + 1 位为黑棋；
blank + 2（黑棋左跳）：需满足第 blank + 2 位为黑棋且第 blank + 1 位为白棋。

题目要求输出序列的字典序最小。输出的数字即为被移动棋子的原位置编号（从 1 起始）。因此，在每一层递归中，我们将所有合法的候选棋子位置 pos 从小到大升序排序，依次尝试转移。只要首次搜索到深度为 $(N+1)^2 - 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#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys

WHITE, EMPTY, BLACK = 1, 0, 2


def search(n: int) -> list[int]:
    """回溯搜索最少步数下字典序最小的跳棋移动序列。"""
    board = [WHITE] * n + [EMPTY] + [BLACK] * n
    target = [BLACK] * n + [EMPTY] + [WHITE] * n
    max_steps = (n + 1) ** 2 - 1
    total_len = 2 * n + 1
    path: list[int] = []

    def dfs(blank: int) -> bool:
        if len(path) == max_steps:
            return board == target

        # 候选移入空格的棋子位置：优先枚举较小下标以保证字典序最小
        moves: list[int] = []
        if blank >= 2 and board[blank - 2] == WHITE and board[blank - 1] == BLACK:
            moves.append(blank - 2)
        if blank >= 1 and board[blank - 1] == WHITE:
            moves.append(blank - 1)
        if blank + 1 < total_len and board[blank + 1] == BLACK:
            moves.append(blank + 1)
        if blank + 2 < total_len and board[blank + 2] == BLACK and board[blank + 1] == WHITE:
            moves.append(blank + 2)

        moves.sort()
        for pos in moves:
            board[blank], board[pos] = board[pos], board[blank]
            path.append(pos + 1)
            if dfs(pos):
                return True
            path.pop()
            board[blank], board[pos] = board[pos], board[blank]
        return False

    dfs(n)
    return path


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    ans = search(n)
    for i in range(0, len(ans), 20):
        print(*(ans[i : i + 20]))


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/**
 * 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-06 11:20
 * update_at: 2026-10-06 11:20
 */
// 经典跳棋互换谜题 (Shuttle Puzzle, USACO 4.4.1)。
// 最少步数恒为 (N+1)^2 - 1：N^2 次跳跃恰好翻转全部异色对，
// 剩下 2N 次相邻平移补足位移。DFS 时按被移动棋子的原下标
// 从小到大尝试，首次到达目标的解即为字典序最小的最优解。

#include <cstdio>

typedef long long ll;

const int MAXN = 30;        // N <= 12，棋盘长度最多 2*12+1 = 25
const int MAXSTEP = (12 + 1) * (12 + 1); // 最深步数 (N+1)^2 - 1 = 168

// 棋盘状态：0 = 空格，1 = 白棋 W，2 = 黑棋 B
int board[MAXN];
int n;                      // 白棋/黑棋个数
int max_steps;              // 最少步数 (N+1)^2 - 1
int path[MAXSTEP];          // path[i] = 第 i 步被移动棋子的原位置（1 起始）
int step_cnt;               // 当前已走步数

// 判断是否已到达目标：左侧 N 个黑棋、中间空格、右侧 N 个白棋
bool is_target() {
    for (int i = 1; i <= n; ++i)
        if (board[i] != 2) return false;   // 左半必须是黑棋
    if (board[n + 1] != 0) return false;   // 中间必须是空格
    for (int i = n + 2; i <= 2 * n + 1; ++i)
        if (board[i] != 1) return false;   // 右半必须是白棋
    return true;
}

// 检查 pos 位置的棋子能否移入 blank 空格（均为 1 起始下标）
bool can_move(int pos, int blank) {
    if (pos < 1 || pos > 2 * n + 1) return false;
    if (blank - pos == 2) return board[pos] == 1 && board[pos + 1] == 2; // 白棋右跳
    if (blank - pos == 1) return board[pos] == 1;                       // 白棋右移
    if (blank - pos == -1) return board[pos] == 2;                      // 黑棋左移
    if (blank - pos == -2) return board[pos] == 2 && board[pos - 1] == 1; // 黑棋左跳
    return false;
}

// 回溯搜索：blank 为当前空格的 1 起始下标
// 返回 true 表示沿当前路径能走到目标状态（即已找到字典序最小的解）
bool dfs(int blank) {
    if (step_cnt == max_steps)
        return is_target(); // 步数已用完，恰好应到达目标

    // 候选位置从小到大枚举，保证输出序列字典序最小
    for (int pos = 1; pos <= 2 * n + 1; ++pos) {
        if (!can_move(pos, blank)) continue;
        // 把 pos 处棋子移入空格：棋子落到 blank，空格来到 pos
        int piece = board[pos]; // 暂存被移动棋子的颜色，便于回溯还原
        board[blank] = piece;
        board[pos] = 0;
        step_cnt++;
        path[step_cnt] = pos; // 输出的就是棋子的 1 起始原下标

        if (dfs(pos)) return true;

        step_cnt--;
        board[pos] = piece; // 回溯还原：棋子回到 pos，blank 恢复为空格
        board[blank] = 0;
    }
    return false;
}

int main() {
    scanf("%d", &n);

    // 初始：下标 1..n 白棋，n+1 空格，n+2..2n+1 黑棋
    for (int i = 1; i <= 2 * n + 1; ++i)
        board[i] = (i <= n) ? 1 : (i == n + 1 ? 0 : 2);

    max_steps = (n + 1) * (n + 1) - 1;
    step_cnt = 0;
    dfs(n + 1); // 空格初始在位置 n+1

    // 每行输出 20 个数
    for (int i = 1; i <= max_steps; ++i) {
        printf("%d", path[i]);
        if (i % 20 == 0 || i == max_steps) printf("\n");
        else printf(" ");
    }
    return 0;
}

复杂度

时间复杂度： $\mathcal{O}((N+1)^2)$ 状态展开。由于棋子严格单向移动且避免了死锁构型，每一步的合法前向转移极少。在 $N \le 12$ 的最大数据下，实际回溯次数仅为 28,618 次，运行时间在几十毫秒以内。
空间复杂度： $\mathcal{O}(N^2)$ 。状态数组长度为 $2N+1$ ，递归调用栈深度与路径记录长度最大为 $(N+1)^2 - 1 = 168$ ，空间占用可忽略不计。

总结

本题是经典的跳棋互换谜题（Shuttle Puzzle）。解题的核心切入点在于分析逆序对与总位移：

每次跳跃必定且只能颠倒一对异色棋子的相对次序，因而必须进行恰好 $N^2$ 次跳跃；
结合总位移守恒确定平移次数必为 $2N$ ，从而严格锁定了最少总步数必然为 $(N+1)^2 - 1$ ；
将步数作为深度限制，按原下标升序贪心枚举转移，使 DFS 能够极快锁定字典序最小的目标解。

图示解析

以 $N=3$ 为例，棋盘长度为 $7$ ，初始空格在位置 $4$ 。游戏状态转移过程如下（共 15 步）：

graph TD
    S0["初始: WWW_BBB"] -->|3号位W右移| S1["WW_WBBB (空格: 3)"]
    S1 -->|5号位B左跳| S2["WWBW_BB (空格: 5)"]
    S2 -->|6号位B左移| S3["WWBWB_B (空格: 6)"]
    S3 -->|4号位W右跳| S4["WWB_BWB (空格: 4)"]
    S4 -->|2号位W右跳| S5["W_BWBWB (空格: 2)"]
    S5 -->|1号位W右移| S6["_WBWBWB (空格: 1)"]
    S6 -->|3号位B左跳| S7["BW_WBWB (空格: 3)"]
    S7 -->|5号位B左跳| S8["BWBW_WB (空格: 5)"]
    S8 -->|7号位B左跳| S9["BWBWBW_ (空格: 7)"]
    S9 -->|6号位W右移| S10["BWBWB_W (空格: 6)"]
    S10 -->|4号位W右跳| S11["BWB_BWW (空格: 4)"]
    S11 -->|2号位W右跳| S12["B_BWBWW (空格: 2)"]
    S12 -->|3号位B左移| S13["BB_WBWW (空格: 3)"]
    S13 -->|5号位B左跳| S14["BBBW_WW (空格: 5)"]
    S14 -->|4号位W右移| S15["BBB_WWW (空格: 4)"]