【例7.6】黑白棋子的移动

题目描述

有 $2n$ 个棋子排成一行（ $n \geqslant 4$ ），最初前 $n$ 个为白子 o，后 $n$ 个为黑子 *，末尾追加两个空位 -。每次选一对相邻棋子整体平移到空位（左右顺序不变，必须跳过若干棋子），要求输出任意一组合法移动序列，使最终局面变成黑白相间的 o*o*…o* 且末尾仍为两个空位。

输入一个整数 $n$ ，输出每一步的局面，格式为 step k:局面。

思路

按固定递归模式推进空位即可： $n > 4$ 时把第 $n, n+1$ 位的 o* 移到空位，再把 ** 移到新空位，规模归约为 $n-1$ ； $n = 4$ 时用固定收尾序列 $\{4,8,2,7,1\}$ 收尾。每次 move(m) 把 a[m],a[m+1] 复制到空位并把空位左移回 $m$ 。

参考代码

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#!/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:27
# update_at: 2026-10-04 13:29

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    size = 2 * n + 2
    a = [''] * (size + 1)                       # 1-index，a[1..2n+2]
    for i in range(1, n + 1):
        a[i] = 'o'
    for i in range(n + 1, size + 1):
        a[i] = '*'
    a[size - 1] = a[size] = '-'                  # 最后两个空位

    st = 0
    sp = size - 1                                # 空位起点

    def out() -> None:
        nonlocal st
        print(f"step{st:2d}:{''.join(a[1:size + 1])}")
        st += 1

    def move(m: int) -> None:
        """把相邻棋子 a[m],a[m+1] 整体移到当前空位 sp,sp+1，空位随之左移。"""
        nonlocal sp
        a[sp] = a[m]
        a[sp + 1] = a[m + 1]
        a[m] = a[m + 1] = '-'
        sp = m
        out()

    out()                                        # step 0：初始局面

    m = n
    while m > 4:
        move(m)
        move(2 * m - 1)
        m -= 1

    # n = 4 时的收尾序列
    for x in (4, 8, 2, 7, 1):
        move(x)


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/**
 * 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 09:53
 * update_at: 2026-10-05 09:53
 */
// main.cpp：2n 个黑白棋子 + 末尾两个空位，按固定递归模式移到黑白相间排列。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105; // n<=50 时 2n+2<=102，开 105 留余量

ll n;                       // 题目规模（白/黑棋子各 n 个）
char a[MAXN];               // a[1..2n+2] 局面，1-index；下标 0 弃用
int sp;                     // 空位起点（sp, sp+1 两个位置为空）

int st;                     // 当前步数

// 输出当前局面作为一步。
void out() {
    cout << "step" << setw(2) << right << st++ << ":";
    for (ll i = 1; i <= 2 * n + 2; i++) cout << a[i];
    cout << "\n";
}

// 把相邻棋子 a[m],a[m+1] 整体移到当前空位 (sp, sp+1)，空位随之回到 m。
void mv(int m) {
    a[sp] = a[m];
    a[sp + 1] = a[m + 1];
    a[m] = '-';
    a[m + 1] = '-';
    sp = m;
    out();
}

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

    cin >> n;

    ll size = 2 * n + 2; // 局面总长
    for (ll i = 1; i <= n; i++) a[i] = 'o';        // 前 n 个白子
    for (ll i = n + 1; i <= size; i++) a[i] = '*'; // 接下来 n 个黑子
    a[size - 1] = a[size] = '-';                   // 末尾两格空位
    sp = size - 1;

    out();                                         // step 0：初始局面

    int m = n;
    while (m > 4) {
        // n>4：先把中间的 o* 推到空位，再把 ** 推到新空位，等效把空位左推 2 格、规模减 1
        mv(m);
        mv(2 * m - 1);
        m -= 1;
    }

    // n=4：固定收尾序列
    int tail[] = {4, 8, 2, 7, 1};
    for (int i = 0; i < 5; i++) mv(tail[i]);

    return 0;
}

【例7.6】黑白棋子的移动

目录

题目描述

思路

参考代码