黑白棋子的移动

题意

有 n 个白子和 n 个黑子，末尾有两个空位。每次移动相邻两个棋子到空位，要求输出从初始状态到黑白相间状态的移动过程。

思路

这题不是搜索最短路，而是按固定规律构造输出。

把规模为 depth 的局面看成：

text

1oooo...****...-- + 已经整理好的 o*o*...

每一层先输出两步，把规模 depth 的问题缩成 depth-1 的问题：

text

1
2oooo****--tail
ooo--***o*tail

当规模缩到 4 时，剩下的收尾过程固定，直接输出 6 行。

Python 知识

字符串可以直接用 char * count 重复。
把所有状态放入 states，最后用 "\n".join(states) 一次输出。
递归函数只负责追加状态，不需要真的模拟棋子数组。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md

代码

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
29def repeated(char, count):
    return char * count


def alternating(count):
    return "o*" * count


def build_states(depth):
    if depth == 4:
        tail = alternating(n - 4)
        states.append("oooo****--" + tail)
        states.append("ooo--***o*" + tail)
        states.append("ooo*o**--*" + tail)
        states.append("o--*o**oo*" + tail)
        states.append("o*o*o*--o*" + tail)
        states.append("--o*o*o*o*" + tail)
        return

    tail_count = n - depth
    states.append(repeated("o", depth) + repeated("*", depth) + "--" + alternating(tail_count))
    states.append(repeated("o", depth - 1) + "--" + repeated("*", depth - 1) + alternating(tail_count + 1))
    build_states(depth - 1)


n = int(input())
states = []
build_states(n)
print("\n".join(states))

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/**
 * 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-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

int n, cnt;
string states[100];

void dfs(int depth) {
    if (depth == 4) {
        string tail = "";
        for (int i = 0; i < n - 4; i++) tail += "o*";
        states[cnt++] = "oooo****--" + tail;
        states[cnt++] = "ooo--***o*" + tail;
        states[cnt++] = "ooo*o**--*" + tail;
        states[cnt++] = "o--*o**oo*" + tail;
        states[cnt++] = "o*o*o*--o*" + tail;
        states[cnt++] = "--o*o*o*o*" + tail;
        return;
    }
    string s = string(depth, 'o') + string(depth, '*') + "--";
    for (int i = 0; i < n - depth; i++) s += "o*";
    states[cnt++] = s;
    s = string(depth - 1, 'o') + "--" + string(depth - 1, '*');
    for (int i = 0; i < n - depth + 1; i++) s += "o*";
    states[cnt++] = s;
    dfs(depth - 1);
}

int main() {
    cin >> n;
    dfs(n);
    for (int i = 0; i < cnt; i++) cout << states[i] << endl;
    return 0;
}

复杂度

输出行数为 $O(n)$ ，每行长度为 $O(n)$ ，总输出规模为 $O(n^2)$ 。额外空间为保存输出状态的 $O(n^2)$ 。

总结

构造输出题要先观察样例规律。这里的核心是每轮把大规模局面缩小一层，最后用固定的 n=4 收尾。

目录

题意

思路

Python 知识

代码

复杂度

总结