usaco training 4.4.1 Shuttle Puzzle 题解

Shuttle Puzzle题解
Traditional

The Shuttle Puzzle of size 3 consists of 3 white marbles, 3 black marbles, and a strip of wood with 7 holes. The marbles of the same color are placed in the holes at the opposite ends of the strip, leaving the center hole empty.

INITIAL STATE: WWW_BBB 
GOAL STATE: BBB_WWW

To solve the shuttle puzzle, use only two types of moves. Move 1 marble 1 space (into the empty hole) or jump 1 marble over 1 marble of the opposite color (into the empty hole). You may not back up, and you may not jump over 2 marbles.

A Shuttle Puzzle of size N consists of N white marbles and N black marbles and 2N+1 holes.

Here's one solution for the problem of size 3 showing the initial, intermediate, and end states:

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

Write a program that will solve the SHUTTLE PUZZLE for any size N (1 <= N <= 12) in the minimum number of moves and display the successive moves, 20 per line.

PROGRAM NAME: shuttle

INPUT FORMAT

A single line with the integer N.

SAMPLE INPUT (file shuttle.in)

3

OUTPUT FORMAT

The list of moves expressed as space-separated integers, 20 per line (except possibly the last line). Number the marbles/holes from the left, starting with one.

Output the the solution that would appear first among the set of minimal solutions sorted numerically (first by the first number, using the second number for ties, and so on).

SAMPLE OUTPUT (file shuttle.out)

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

描述

大小为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)。要求用最少的移动步数实现。

格式

PROGRAM NAME: shuttle

INPUT FORMAT:

(file shuttle.in)

一个整数N。

OUTPUT FORMAT:

(file shuttle.out)

输出用移动的棋子在棋盘的位置(位置从左到右依次为1, 2, ..., 2N+1)表示的变换序列，每个数字之间以空格分隔，每行20个数(除了最后一行)。

输出的解还应当有最小的字典顺序(即如果有多组移动步数最小的解，输出第一个数最小的解；如果还有多组，输出第二个数最小的解；...)。

SAMPLE INPUT

3

SAMPLE OUTPUT

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

-----------------------------------------------------------分割线---------------------------------------------------------------------

       

刚开始看这道题毫无头绪。N<=12，心想着可能又是搜索+剪枝。于是我就直接打开NOCOW上的题解。

太神了！一大牛的找规律把握吓傻了！

Usaco在这题上并没有指明不可以用分析法，而且dfs肯定TLE，所以我们取巧。

先观察样例数据，如果把还没移动的那一步也算上，那么空格的位置为

4 3 5 6 4 2 1 3 5 7 6 4 2 3 5 4 (n=3,样例)

5 4 6 7 5 3 2 4 6 8 9 7 5 3 1 2 4 6 8 7 5 3 4 6 5 (n=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

对于第n+2~2n+1组，可以由对称性求出。了！一大牛的找规律把握吓傻了！

我就根据他那强大的公式编了个程序，然后0.000s秒过。。

于是我开始想了，汉诺塔问题有规律吗？……

代码：

/*
ID:juan1973
LANG:C++
TASK:shuttle
*/
#include<stdio.h>
using namespace std;
int a[101][101];
int start,n,i,j;
int main()
{
  freopen("shuttle.in","r",stdin);
  freopen("shuttle.out","w",stdout);
  scanf("%ld",&n);int cnt=0;
  a[1][1]=n+1;a[1][0]=1;
  for (i=2;i<=n+1;i++)
    if (a[i-1][1]%2==1)
    {
      a[i][0]=a[i-1][0]+1;
      if (n%2==0)
      {
        start=n-i;
        for (j=1;j<=a[i][0];j++)
        {
          start+=2;
          a[i][j]=start;
          cnt++;
          if (cnt%20==0) printf("%ld\n",a[i][j]);
          else printf("%ld ",a[i][j]);
        }
      }
      else
      {
        start=n-i+2+2*a[i][0];
        for (j=1;j<=a[i][0];j++)
        {
          start-=2;
          a[i][j]=start;
          cnt++;
          if (cnt%20==0) printf("%ld\n",a[i][j]);
          else printf("%ld ",a[i][j]);
        }
      }
    }
    else 
    {
      if (n%2==0)
      {
        a[i][0]=a[i-1][0]+1;
        start=n+i+2;
        for (j=1;j<=a[i][0];j++)
        {
          start-=2;
          a[i][j]=start;
          cnt++;
          if (cnt%20==0) printf("%ld\n",a[i][j]);
          else printf("%ld ",a[i][j]);
        }
      }
      else
      {
        a[i][0]=a[i-1][0]+1;
        start=n+i-2*a[i][0];
        for (j=1;j<=a[i][0];j++)
        {
          start+=2;
          a[i][j]=start;
          cnt++;
          if (cnt%20==0) printf("%ld\n",a[i][j]);
          else printf("%ld ",a[i][j]);
        }
      }
    }
  for (i=n;i>1;i--)
    for (j=1;j<=a[i][0];j++)
    {
      cnt++;
      if (cnt%20==0) printf("%ld\n",a[i][j]);
      else printf("%ld ",a[i][j]);
    }
  printf("%ld\n",n+1);
  return 0;
}