若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1473: 4.4.1 Shuttle Puzzle 棋盘游戏

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,429

题目描述

大小为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。

输出

用空格在棋盘的位置(位置从左到右依次为1, 2, …, 2N+1)表示棋盘的状态。输出棋盘的状态变换序列,每行20个数(除了最后一行)。

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

样例输入

3

样例输出

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

参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Skip 原站点 Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist