P2739 [USACO4.4]棋盘游戏Shuttle Puzzle[找规律]

题目描述

大小为3的棋盘游戏里有3个白色棋子,3个黑色棋子,和一个有7个格子一线排开的木盒子。3个白棋子被放在一头,3个黑棋子被放在另一头,中间的格子空着。
初始状态: WWW_BBB
目标状态: BBB_WWW
在这个游戏里有两种移动方法是允许的:
你可以把一个棋子移到与它相邻的空格;
你可以把一个棋子跳过一个(仅一个)与它不同色的棋子到达空格。

大小为N的棋盘游戏包括N个白棋子,N个黑棋子,还有有2N+1个格子的木盒子。
这里是3-棋盘游戏的解,包括初始状态,中间状态和目标状态:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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。

输出格式:

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

输入输出样例

输入样例#1:

3

输出样例#1:

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

说明

题目翻译来自NOCOW。
USACO Training Section 4.3

题解

根据n=3和n=4直接找规律.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
int i,j;
int p1,p2;
int d1,d2;
int ans;
int xx;
int read()//读入
{
char ch=getchar();
int x=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x;
}
int main()
{
//freopen("shuttle.in","r",stdin);
//freopen("shuttle.out","w",stdout);
n=read();
p1=n-1;
d1=n+2;
p1+=2;
for (i=2;i<=n+1;i++)
{
if (i%2==1)
{
/*435 642 1357 642 35 4 (n=3,样例)
5 46 753 2468 97531 2468 753 46 5 (n=4)*/
p1+=2;p2=p1;
for (j=1;j<=i;j++)
{
if (ans==0) printf("%d",p2); else printf(" %d",p2);
ans++;
if (ans==20) printf("\n"),ans=0;//格式
if (j!=i) p2-=2;
}
} else
{
d1-=2;d2=d1;
for (j=1;j<=i;j++)
{
if (ans==0) printf("%d",d2); else printf(" %d",d2);
ans++;
if (ans==20) printf("\n"),ans=0;//格式
if (j!=i) d2+=2;
}
}
}
//p1+=2;
//
//d1-=2;
if (n%2==1) p1+=2;
if (n%2==0) d1-=2;
for (i=n;i>=1;i--)
{
if (i%2==1)
{
/*435 642 1357 642 35 4 (n=3,样例)
5 46 753 2468 97531 2468 753 46 5 (n=4)*/
p1-=2;p2=p1;
for (j=1;j<=i;j++)
{
if (ans==0) printf("%d",p2); else printf(" %d",p2);
ans++;
if (ans==20) printf("\n"),ans=0;//格式
if (j!=i) p2-=2;
}
} else
{
d1+=2;d2=d1;
for (j=1;j<=i;j++)
{
if (ans==0) printf("%d",d2); else printf(" %d",d2);
ans++;
if (ans==20) printf("\n"),ans=0;//格式
if (j!=i) d2+=2;
}
}
}
return 0;
}