网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
分球
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | balls.in | 输出文件 | balls.out |
【问题描述】
在一个装满财宝的屋子里,有2N个盒子排成一排。除了两个相邻的空盒外,其余的每个盒子里都装有一个金球或者一个银球,总共有N-1个金球和N-1个银球。用图6.3所示为一个N=5时的例子,G表示金球,S表示银球。
G
|
S
|
S
|
G
|
|
|
G
|
S
|
G
|
S
|
任意两个相邻的非空的盒子里的球可以移动到两个相邻的空盒中,移动不能改变这两个球的排列顺序。写一个程序,用最少的移动次数把所有的金球都移到所有的银球的左边。
【输入格式】
输入文件包含多组数据。第一行为K,表示数据的总数。
每组数据的第一行是N(3≤N≤7),
第二行是2N个盒子的初始状态。金球用a表示, 银球用b表示,空盒用空格表示。每两组相邻数据用空行隔开。
【输出格式】
对于每一组数据,若无解则输出一行NO SOLUTION,若有解,输出一组状态来表示移动的序列,每个状态占一行。每行输出到此状态的移动的步数,紧接着是一个空格,然后是此时的状态。初始状态为第0步,每组数据都要先输出初始状态。如有多种最少移动次数的方案,输出“空格靠前靠左”的一种,如下两种方案,需输出第二种。
0 bbbb aaaa
1 bbbbaa aa
2 bbaabbaa
3 aabbaabb
4 aa aabbbb
1 bbbbaa aa
2 bbaabbaa
3 aabbaabb
4 aa aabbbb
0 bbbb aaaa
1 bbbbaaaa
2 aabbbb aa
3 aa bbbbaa
4 aaaabbbb
1 bbbbaaaa
2 aabbbb aa
3 aa bbbbaa
4 aaaabbbb
相邻的两组数据用一个空行隔开。
【输入输出样例】
样例输入(balls.in):
3 3 abab 5 abba abab 6 a babbababa
样例输出(balls.out):
NO SOLUTION 0 abba abab 1 abbabaa b 2 a abaabbb 3 aaaab bbb 0 a babbababa 1 aabbabb aba 2 aabbabbbaa 3 aa abbbaabb 4 aaaaabbb bb