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 BWBWBWBWBWB 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個黑棋子被放在另一頭，中間的格子空著。

初始狀態(tài): WWW_BBB 目標狀態(tài): BBB_WWW

在這個游戲里有兩種移動方法是允許的：

你可以把一個棋子移到與它相鄰的空格；

你可以把一個棋子跳過一個(僅一個)與它不同色的棋子到達空格。

大小為N的棋盤游戲包括N個白棋子，N個黑棋子，還有有2N+1個格子的木盒子。

這里是3-棋盤游戲的解，包括初始狀態(tài)，中間狀態(tài)和目標狀態(tài)：

WWW BBBWW WBBBWWBW BBWWBWB BWWB BWBW BWBWBWBWBWBBW WBWBBWBW WBBWBWBW BWBWB WBWB BWWB BWBWWBB WBWWBBBW WWBBB 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上的題解。

太神了！一大牛的找規(guī)律把握嚇傻了！

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)

我們憑借極其敏銳的眼光發(fā)現這組序列為

４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組，可以由對稱性求出。了！一大牛的找規(guī)律把握嚇傻了！

我就根據他那強大的公式編了個程序，然后0.000s秒過。。

于是我開始想了，漢諾塔問題有規(guī)律嗎？……

代碼：

/* 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; }

總結

以上是生活随笔為你收集整理的usaco training 4.4.1 Shuttle Puzzle 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。