【题目描述】
有2n个棋子(n≥4)排成一行,开始位置为白子全部在左边,黑子全部在右边,如下图为n=5的情形:○○○○○●●●●●
移动棋子的规则是:每次必须同时移动相邻的两个棋子,颜色不限,可以左移也可以右移到空位上去,但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子(不能平移),要求最后能移成黑白相间的一行棋子。如n=5时,成为:○●○●○●○●○●
任务:编程打印出移动过程。
【输入】
输入n。
【输出】
移动过程。
【输入样例】
7
【输出样例】
step 0:ooooooo*******--
step 1:oooooo--******o*
step 2:oooooo******--o*
step 3:ooooo--*****o*o*
step 4:ooooo*****--o*o*
step 5:oooo--****o*o*o*
step 6:oooo****--o*o*o*
step 7:ooo--***o*o*o*o*
step 8:ooo*o**--*o*o*o*
step 9:o--*o**oo*o*o*o*
step10:o*o*o*--o*o*o*o*
step11:--o*o*o*o*o*o*o*
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
#define INF 999999999
#define N 1001
#define MOD 1000000007
using namespace std;
int n,st,sp;
char a[N];
void print()
{
printf("step%2d:",st++);
for(int i=1;i<=2*n+2;i++)
printf("%c",a[i]);
printf("\n");
}
void move(int m)
{
a[sp]=a[m];
a[sp+1]=a[m+1];
a[m]=a[m+1]='-';
sp=m;
print();
}
void mv(int m)
{
if(m==4)
{
move(4);
move(8);
move(2);
move(7);
move(1);
}
else
{
move(m);
move(2*m-1);
mv(m-1);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
a[i]='o';
for(int i=n+1;i<=2*n;i++)
a[i]='*';
for(int i=2*n+1;i<=2*n+2;i++)
a[i]='-';
st=0;
sp=2*n+1;
print();
mv(n);
return 0;
}
信息学奥赛一本通T1327:分治算法 黑白棋子的移动 归属于 分治算法,更多同类题解源程序见:分治算法 和 黑白棋子的移动
0 篇文章
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!