【题解】【分治】——黑白棋子的移动

黑白棋子的移动

通往洛谷的传送门

题目描述

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

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

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

输入格式

一个整数 $n$。

输出格式

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

输入输出样例

输入 #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$

1.题意解析

    仔细观察，可以发现，移动规模为$n$的棋子，可以现将中间的两枚o*棋子移到最后，然后将*行的最后两个移到空位上来，形成了规模为$n-1$的子问题，可以使用递归来解决，具体示例如下：

n=5时：
ooooo*****__。
将中间的o*用x代替，使演示更为直观。
ooooo*****__。
移动步骤一，oooo__****xx。
再将x旁边的两个棋子*替换为y。
oooo__**yyxx
移动步骤二，ooooyy**__xx。
再把字母替换回来：
oooo****__o*
可以发现，前面的$4\ast 2=8$个格子形成了规模为$5-1=4$的子问题。

    但是，看看样例$n=4$时是特殊情况，也是递归边界。这个时候，我们就直接输出就行了。详见代码。

2.AC代码

#include<bits/stdc++.h>
using namespace std;
int n;
char a[210];//存储棋盘 
void start()//初始化棋盘 
{for(int i=1;i<=n;i++)a[i]='o',a[i+n]='*';a[2*n+1]=a[2*n+2]='-';
}
void print()//打印棋盘
{for(int i=1;i<=n*2+2;i++)cout<<a[i];cout<<endl;
}
void move(int x)//移动棋子,x代表当前规模 
{if(x==4)//递归边界,x=4时是特殊情况 {cout<<"ooo--***o*";//第一次移动for(int i=1;i<=n-4;i++)cout<<'o'<<'*';//补位puts("");//换行cout<<"ooo*o**--*";//以此类推 for(int i=1;i<=n-4;i++)cout<<'o'<<'*';puts("");cout<<"o--*o**oo*";for(int i=1;i<=n-4;i++)cout<<'o'<<'*';puts("");cout<<"o*o*o*--o*";for(int i=1;i<=n-4;i++)cout<<'o'<<'*';puts("");cout<<"--o*o*o*o*";for(int i=1;i<=n-4;i++)cout<<'o'<<'*';return;}swap(a[x],a[2*x+1]);swap(a[x+1],a[2*x+2]);print();//平常情况的第一步swap(a[2*x-1],a[x]);swap(a[2*x],a[x+1]);print();//平常情况的第二步move(x-1);//递归处理 return;
}
int main()
{cin>>n;start();print();//开始先打印棋盘 move(n);//移动棋子 return 0;
}

喜欢就订阅此专辑吧！

【蓝胖子编程教育简介】
蓝胖子编程教育，是一家面向青少年的编程教育平台。平台为全国青少年提供最专业的编程教育服务，包括提供最新最详细的编程相关资讯、最专业的竞赛指导、最合理的课程规划等。本平台利用趣味性和互动性强的教学方式，旨在激发孩子们对编程的兴趣，培养他们的逻辑思维能力和创造力，让孩子们在轻松愉快的氛围中掌握编程知识，为未来科技人才的培养奠定坚实基础。

欢迎扫码关注蓝胖子编程教育