题目描述

有 2n个棋子排成一行，开始为位置白子全部在左边，黑子全部在右边，如下图为 n=5 的情况：

○○○○○●●●●●

移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如 n=5 时，成为：

○●○●○●○●○●

任务：编程打印出移动过程。

输入格式

一个整数 n。

输出格式

若干行，表示初始状态和每次移动的状态，用"o"表示白子，"*“表示黑子，”-"表示空行。

题目分析

当n = 4 时

初始时，○○○○●●●●

  1. ○○○— —●●●○●
  2. ○○○●○●●— —●
  3. ○— —●○●●○○●
  4. ○●○●○●— —○●
  5. — —○●○●○●○●

当n = 5 时,

初始时，○○○○○●●●●●

  1. ○○○○— —●●●●○●
  2. ○○○○●●●●— —○●

​ 可以看出当n=5时，在第二步结束后，问题就变成了n=4时的场景，故本题可使用分治法，通过将规模为n的问题分解为规模为n-1的原问题和另一个可以直接解决的子问题。

代码编写

定义数据结构，本题使用数组作为棋盘的数据结构，数组定义如下，

1
2
3
4
5
// 整个棋盘，下标取值范围为[1,100], 0下标空下
// 1~n存放白子
// n+1~2n存放黑子
// 2n+1, 2n+2为空位
char c[101];

定义输入参数为n

1
2
// 黑棋或白棋的个数
int n;

每次空位移动后，记录移动之后sp指针(space point)的变化，方便下次移动寻找空位。

1
2
3
// 记录空位的指针
int sp;

定义打印棋盘的函数

1
2
3
4
5
6
7
// 打印结果
void output(){
    for(int i=1;i<=2*n+2;i++){
        cout<<c[i];
    }
    cout<<endl;
}

初始化最初的棋盘

1
2
3
4
5
6
7
8
9
10
11
12
// 初始化棋盘
void init(){
    // 白子初始化
    for (int i=1;i<=n;i++) c[i]='o';
    // 黑子初始化
	for (int i=n+1;i<=2*n;i++) c[i]='*';
    // 空位初始化
    c[2*n+1] = c[2*n+2] = '-';
    // 空位指针初始化
    sp = 2*n+1;
    output();
}

定义第k与k+1个棋子与空格交换位置的函数

1
2
3
4
5
6
7
8
9
10

// 移动第k个和k+1个棋子与空位交换位置
void move(int k){
    // 分别移动两个空位和两个棋子
    swap(c[sp],c[k]);
    swap(c[sp+1],c[k+1]);
    // 更新sp指针
    sp = k;
    output();
}

递归求解函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void run(int n){
    // n == 4时为问题的初值，需要特殊求解
    if(n==4){
        move(4); 
        move(8); 
        move(2); 
        move(7); 
        move(1);
    }else{
        // 第一步移动中间的n,n+1棋子到空位
        move(n);
        // 第二步移动2n-1,2n棋子到空位
        move(2*n-1);
        // 开始求解规模为n-1的子问题
        run(n-1);
    }
}

整个程序如下

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
#include <bits/stdc++.h>

using namespace std;

// 整个棋盘，下标取值范围为[1,100], 0下标空下
// 1~n存放白子
// n+1~2n存放黑子
// 2n+1, 2n+2为空位
char c[101];    
// 黑棋或白棋的个数
int n;

// 记录空位的指针
int sp;

// 打印结果
void output(){
    for(int i=1;i<=2*n+2;i++){
        cout<<c[i];
    }
    cout<<endl;
}

// 初始化棋盘
void init(){
    // 白子初始化
    for (int i=1;i<=n;i++) c[i]='o';
    // 黑子初始化
	for (int i=n+1;i<=2*n;i++) c[i]='*';
    // 空位初始化
    c[2*n+1] = c[2*n+2] = '-';
    // 空位指针初始化
    sp = 2*n+1;
    output();
}

// 移动第k个和k+1个棋子与空位交换位置
void move(int k){
    // 分别移动两个空位和两个棋子
    swap(c[sp],c[k]);
    swap(c[sp+1],c[k+1]);
    // 更新sp指针
    sp = k;
    output();
}

void run(int n){
    // n == 4时为问题的初值，需要特殊求解
    if(n==4){
        move(4); move(8); move(2); move(7); move(1);
    }else{
        // 第一步移动中间的n,n+1棋子到空位
        move(n);
        // 第二步移动2n-1,2n棋子到空位
        move(2*n-1);
        // 开始求解规模为n-1的子问题
        run(n-1);
    }
}

int main(){
    cin>>n;
    init();
    run(n);
    return 0;
}