| 题目名称 | 893. 棋盘游戏 |
|---|---|
| 输入输出 | shuttleus.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 sywgz
于2012-07-11加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：7， 提交：22， 通过率：31.82% | ||||
 任杰 |
100 | 0.002 s | 0.31 MiB | C++ |
|
任杰 |
100 | 0.003 s | 0.31 MiB | C++ |
 xinging |
100 | 0.003 s | 0.62 MiB | C++ |
 CAX_CPG |
100 | 0.014 s | 0.17 MiB | Pascal |
|
CAX_CPG |
100 | 0.014 s | 0.17 MiB | Pascal |
 cstdio |
100 | 0.069 s | 0.31 MiB | C++ |
|
mildark |
100 | 0.071 s | 0.31 MiB | C++ |
 hahaha |
90 | 1.140 s | 42.35 MiB | C++ |
|
hahaha |
90 | 1.306 s | 42.35 MiB | C++ |
|
mildark |
80 | 2.088 s | 27.33 MiB | C++ |
| 关于 棋盘游戏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
没有办法，小时候跳棋玩的好
xinging
2015-02-28 19:12
3楼
| ||||
|
回复 @TCtower :
= =那你是怎么AC的  HouJikan
2014-09-20 09:52
2楼
| ||||
|
BFS+set判重过6组
BFS+hash判重过6~8组（取决于MODer，拜RP之神） 好神奇的赶脚，考试的时候估计也就这样了= = | ||||
USACO/shuttleus(译by Jeru)
描述
大小为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: shuttleus
INPUT FORMAT(file shuttleus.in)
一个整数N。
OUTPUT FORMAT(file shuttleus.out)
用空格在棋盘的位置(位置从左到右依次为1, 2, ..., 2N+1)表示棋盘的状态。输出棋盘的状态变换序列，每行20个数(除了最后一行)。
输出的解还应当有最小的字典顺序(即如果有多组移动步数最小的解，输出第一个数最小的解；如果还有多组，输出第二个数最小的解；...)。
SAMPLE INPUT (file shuttleus.in)
3
3 5 6 4 2 1 3 5 7 6 4 2 3 5 4