题目名称	641. 分球
输入输出	`balls.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	8
题目来源	cqw 于2012-02-17加入
开放分组	全部用户
提交状态
分类标签	搜索法
	分享题解

通过：10，提交：50，通过率：20%
Truth.Cirno	100	0.230 s	11.69 MiB	C++
Makazeu	100	0.273 s	83.23 MiB	C++
Makazeu	100	0.445 s	166.20 MiB	C++
Czb。	100	0.550 s	41.26 MiB	C++
cqw	100	0.669 s	43.18 MiB	C++
Citron酱	100	0.672 s	0.27 MiB	C++
Oo湼鞶oO	100	0.673 s	0.27 MiB	C++
王者自由	100	0.707 s	31.73 MiB	C++
王者自由	100	0.863 s	42.22 MiB	C++
王者自由	100	1.169 s	63.20 MiB	C++

本题关联比赛
20120217

关于分球的近10条评论(全部评论)

641. 分球

★☆ 输入文件：balls.in 输出文件：balls.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

在一个装满财宝的屋子里，有2N个盒子排成一排。除了两个相邻的空盒外，其余的每个盒子里都装有一个金球或者一个银球，总共有N-1个金球和N-1个银球。用图6．3所示为一个N=5时的例子，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

0 bbbb aaaa
         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