Shuttle Puzzle

题目描述

大小为3的棋盘游戏里有3个白色棋子，3个黑色棋子，和一个有7个格子一线排开的木盒子。3个白棋子被放在一头，3个黑棋子被放在另一头，中间的格子空着。

初始状态: WWW_BBB

目标状态: BBB_WWW

在这个游戏里有两种移动方法是允许的：

1.你可以把一个棋子移到与它相邻的空格；

2.你可以把一个棋子跳过一个(仅一个)与它不同色的棋子到达空格。

大小为N的棋盘游戏包括N个白棋子，N个黑棋子，还有有2N+1个格子的木盒子。

这里是3-棋盘游戏的解，包括初始状态，中间状态和目标状态：

 WWW BBB

 WW WBBB

 WWBW BB

 WWBWB B

 WWB BWB

 W BWBWB

 WBWBWB

 BW WBWB

 BWBW WB

 BWBWBW

 BWBWB W

 BWB BWW

 B BWBWW

 BB WBWW

 BBBW WW

 BBB WWW

请编一个程序解大小为N的棋盘游戏(1 <= N <= 12)。要求用最少的移动步数实现。

输入

包含多组测试用例，每个测试用例占一行，每行包含一个整数N，表示棋盘的大小N，输入0程序结束。

输出

对一个测试用例：输出用移动的棋子在棋盘的位置(位置从左到右依次为1, 2, ..., 2N+1)表示的变换序列，每个数字之间以空格分隔，每行20个数(除了最后一行)。 输出的解还应当有最小的字典顺序(即如果有多组移动步数最小的解，输出第一个数最小的解；如果还有多组，输出第二个数最小的解；...)。

样例输入

3
0

样例输出

3 5 6 4 2 1 3 5 7 6 4 2 3 5 4

大犇凭借极其敏锐的眼光发现这组序列为
４35 642 1357 642 35 4 (n=3,样例)
5 46 753 2468 97531 2468 753 46 5 (n=4)
即长度为1,2,3,4,...,n,n+1,n,...,4,3,2,1这样的2n+1组等差序列(长度是指数字的个数,不是指总的长度)
我们讨论第1~n+1组序列，这些序列满足
　　*公差的绝对值为2
　　*奇数组为降序列，偶数组为升序列
　　*对于第i组(1<=i<=n+1),若为奇数组则首项为n+i，偶数组则首项为n-i+2

code:

#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#define M 25
#define INF 0x7fffffff
typedef long long ll;
using namespace std;
int n;
int num[M][M];
void solve()
{
    memset(num,-1,sizeof(num));
    int i,j,t=1,t1,t2;
    for(i=1; i<=n+1; ++i)
    {
        int x,k=0;
        if(i&1)     //若为奇数组则首项为n+i，
        {
            x=n+i;
            t1=x;
            num[i][k++]=t1;
            for(j=0; j<i-1; ++j)
            {
                x-=2;
                t1=x;
                num[i][k++]=t1;
            }
            }
        else       //偶数组则首项为n-i+2
        {
            x=n-i+2;
            t2=x;
            num[i][k++]=t2;
            for(j=0; j<i-1; ++j)
            {
                x+=2;
                t2=x;
                num[i][k++]=t2;
            }
        }
    }
    for(i=2;i<=n+1;++i){
        for(j=0;num[i][j]!=-1;++j){
          //  printf("%d",)
            if(t%20==0)printf("%d\n",num[i][j]);
            else
                printf("%d ",num[i][j]);
            t++;
        }
    }
    if(t%20==0)
        printf("\n%d",num[n][0]);
    else
        printf("%d",num[n][0]);
    for(i=n;i>=1;--i)
    {
        for(j=0;num[i][j]!=-1;++j)
        {
            if(i==n&&j==0) continue;
             if(t%20==0)printf("\n%d",num[i][j]);
            else
                printf(" %d",num[i][j]);
            t++;
        }
    }
    printf("\n");
}
int main()
{
   // freopen("xx.in","r",stdin);
  //  freopen("xx.out","w",stdout);
    while(scanf("%d",&n),n)
    {
       // printf("%d=\n",n);
       solve();
    }
    //cout << "Hello world!" << endl;
    return 0;
}