题解 P1259 【黑白棋子的移动】

HeartBlock_Love · 2019-08-08 22:49:08 · 题解

【算法分析】

我们先从n=4开始试试看，初始时：

       ○○○○●●●●

第1步：○○○——●●●○● {—表示空位}

第2步：○○○●○●●——●

第3步：○——●○●●○○●

第4步：○●○●○●——○●

第5步：——○●○●○●○●

  如果n=5呢？我们继续尝试，希望看出一些规律，初始时：

       ○○○○○●●●●●

第1步： ○○○○——●●●●○●

第2步： ○○○○●●●●——○●

这样，n=5的问题又分解成了n=4的情况，下面只要再做一下n=4的5个步骤就行了。同理，n=6的情况又可以分解成n=5的情况，……，所以，对于一个规模为n的问题，我们很容易地就把他分治成了规模为n-1的相同类型子问题。

  数据结构如下：数组c[1..max]用来作为棋子移动的场所，初始时，c[1]~c[n]存放白子（用字符o表示），c[n+1]~c[2n]存放黑子（用字符*表示），c[2n+1]，c[2n+2]为空位置（用字符—表示）。最后结果在c[3]~c[2n+2]中。

#include<iostream>
using namespace std;
int n,st,sp;
char c[101];
void print()                                  //打印
{
    int i;
    cout<<"step "<<st<<':';
    for (i=1;i<=2*n+2;i++) cout<<c[i];
    cout<<endl;
    st++;
}
void init(int n)                             //初始化
{
    int i;
    st=0;
    sp=2*n+1;
    for (i=1;i<=n;i++) c[i]='o';
    for (i=n+1;i<=2*n;i++) c[i]='*';
    c[2*n+1]='-';c[2*n+2]='-';
    print();
}
void move(int k)                            //移动一步
{
    int j;
    for (j=0;j<=1;j++) 
    {
       c[sp+j]=c[k+j];
       c[k+j]='-';
    }
    sp=k;
    print();
}
void mv(int n)                                       //主要过程
{
    int i,k;
    if (n==4)                //n等于4的情况要特殊处理
    {
        move(4); move(8); move(2); move(7); move(1);
        }
    else
    {
        move(n); move(2*n-1); mv(n-1);
        }
}
int main()
{
    cin>>n;
    init(n);
    mv(n);
}