信息学奥赛一本通T1327：分治算法 黑白棋子的移动

【题目描述】有2n个棋子（n≥4）排成一行，开始位置为白子全部在左边，黑子全部在右边，如下图为n=5的情形：○○○○○●●●●●移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如n=5时，成为：○●○●○●○●○●任务：编程打印出移动过程。【输入】输入n

信息学奥赛一本通T1327：黑白棋子的移动

【题目描述】

有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 条评论

请先 登录 后评论
不写代码的码农
轩爸

0 篇文章

作家榜 »

  1. admin 2 文章
  2. 张芳 0 文章
  3. hanna 0 文章
  4. Jason 0 文章
  5. lixiaioqian 0 文章
  6. GeraldWrora 0 文章
  7. 董伟 0 文章
  8. 信奥达人 0 文章

轩爸

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！