P1259 黑白棋子的移动 题解

题目描述

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

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

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

输入格式

一个整数 $n$。

输出格式

若干行，表示初始状态和每次移动的状态，用 $\verb!o!$ 表示白子，$\verb!*!$ 表示黑子，$\verb!-!$ 表示空行。

Speical Judge

样例 #1

样例输入 #1

7

样例输出 #1

ooooooo*******--
oooooo--******o*
oooooo******--o*
ooooo--*****o*o*
ooooo*****--o*o*
oooo--****o*o*o*
oooo****--o*o*o*
ooo--***o*o*o*o*
ooo*o**--*o*o*o*
o--*o**oo*o*o*o*
o*o*o*--o*o*o*o*
--o*o*o*o*o*o*o*

提示

$ 4\leq n\leq 100$

题解

看着似乎没有头绪？我们不妨先按照样例所示的规律来用纸笔画一画

0 1 2 3 4 5 6 7 8 9 10 11 12 13
ooooooo*******--
oooooo--******o*
oooooo******--o*
ooooo--*****o*o*
ooooo*****--o*o*
oooo--****o*o*o*
oooo****--o*o*o*
ooo--***o*o*o*o*
ooo*o**--*o*o*o*
o--*o**oo*o*o*o*
o*o*o*--o*o*o*o*
--o*o*o*o*o*o*o*

然后再考虑几种简单的

0 1 2 3 4 5 6 7 8 9
oooo****--
ooo--***o*
ooo*o**--*
o--*o**oo*
o*o*o*--o*
--o*o*o*o*

0 1 2 3 4 5 6 7 8 9 10 11
ooooo*****--
oooo--****o*
oooo****--o*
ooo--***o*o*
ooo*o**--*o*
o--*o**oo*o*
o*o*o*--o*o*
--o*o*o*o*o*

这个时候我们可以注意到如下几个细节：

1. 最后5行的规律总是相同的：即

   ooo--***o*
   ooo*o**--*
   o--*o**oo*
   o*o*o*--o*
   --o*o*o*o*

   再在末尾跟上n-4个"o*"

2. 前面部分的移动规律：考虑i从第n个开始，交换i和i+i+1的位置，交换i-1和i-1+i+1的位置，输出改变之后的字符串；然后再交换i和i+i-1的位置，交换i-1和i-1+i-1的位置，再输出

   (这样的规律是如何发现的？可以多写出来诸如这样的部分

   开始(n=7时)	第一次交换的下标	第二次交换的下标
   i=7	15	13
   i-1=6	14	12
   i=6	13	11
   i-1=5	12	10
   i=5	11	9
   i-1=4	10	8
   差值	i+1	i-1

   得到差值之后也就轻松了。

   )

   这样的移动操作总共需要进行n-4次，也就是i从n遍历到5即可

   （为什么是n-4次？也可以从最后的角度考虑，我们要创造出n-4个"o*"，而每进行一次这样的操作就是会多一个"o*"的结构

于是我们就可以进行代码实现了

#include<bits/stdc++.h>
using namespace std;
void move(int n){
    string s;
    //初始化
    for(int i=0;i<n;i++){
        s.push_back('o');
    }
    for(int i=n;i<2*n;i++){
        s.push_back('*');
    }
    s.push_back('-');
    s.push_back('-');
    cout<<s<<endl;
    //进行改变
    for(int i=n;i>=5;i--){
        swap(s[i],s[2*i+1]);
        swap(s[i-1],s[2*i]);
        cout<<s<<endl;
        swap(s[i],s[2*i-1]);
        swap(s[i-1],s[2*i-2]);
        cout<<s<<endl;
    }
    //定义尾部字符串
    string s0;
    for(int i=0;i<2*(n-4);i+=2){
        s0.push_back('o');
		s0.push_back('*');
    }
    cout<<"ooo--***o*"<<s0<<endl;
    cout<<"ooo*o**--*"<<s0<<endl;
    cout<<"o--*o**oo*"<<s0<<endl;
    cout<<"o*o*o*--o*"<<s0<<endl;
    cout<<"--o*o*o*o*"<<s0;
}
int main(){
    int n;
    cin>>n;
    move(n);
}

还有一个需要注意的点

这样去初始化字符串

for(int i=0;i<2*(n-4);i+=2){
    s0[i]='o';
    s0[i+1]='*';
}

是不可以的。因为直接通过下标访问一个空字符串的字符是未定义行为（undefined behavior），这可能导致程序崩溃或没有任何输出。

正确做法：统一使用push_back()函数。