1． 中国盒问题

2*N个盒子一个接一个地排在一行，有两个相邻的盒子是空着的，其他盒子中有N－1个符号“A”和N－1个符号“B”，例如在N＝5时有：ABBA____ABAB。交换规则：两个相邻的非空盒子中的符号可移至两个空盒中，移时不得改变两符号顺序。目标：让所有符号“A”都出现在所有符号“B”的左边 ，不管空盒在什么位置。

问题：编写一个程序，满足：（1）键盘输入由“A”、“B”和0（表示空盒）构成的初始状态序列和交换方式。（2）对一个给定的初始状态，找出至少一种达到目标的交换方案，或者报告找不到方案，输出应包括初始状态，每一步中间状态和最后在到的状态。（3）对上面所举的例子至少应给出一解。