04-08移动字母

移动字母

2x3=6个方格中放入ABCDE五个字母,右下角的那个格空着。如图所示

和空格子相邻的格子中的字母可以移动到空格中,比如,图中的C和E就可以移动,移动后的局面分别是:

A B

D E C

A B C

D E

为了表示方便,我们把6个格子中字母配置用一个串表示出来,比如上边的两种局面分别表示为:

AB*DEC

ABCD*E

题目的要求是:请编写程序,由用户输入若干表示局面的串,程序通过计算,输出是否能通过对初始状态经过若干次移动到达该状态。可以实现输出1,否则输出0。初始状态为:ABCDE*

用户输入的格式是:先是一个整数n,表示接下来有n行状态。程序输出也应该是n行1或0

例如,用户输入:/p>

3

ABCDE*

AB*DEC

CAED*B

则程序应该输出:

1

1

0

--------------------------------------------------------------------------------------------------------------------------------



可以这样看,字母的移动与唯一的“空格”的移动具是等效的。


我们可以考虑空格的移动,这样更简便。


由初始状态开始,移动空格后,形成新的状态。不断地增加新的状态,直到包含了所有的可能状态。




也可以递归的想法:


  由初始状态一步就可以达到的状态判为有解;


  否则,由衍生状态继续递归求解。


  为防止无限期地调用下去,必须考虑结束递归的条件。比如:考虑递归深度不能超过总的格子的数目

04-08移动字母,,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。