用编程思想解决游戏中的谜题-BFS(宽度优先搜索)

最近入了一款游戏 chronicon, 类暗黑2, 像素画风 游戏性还行。其中有一个小游戏：有9个由3个三种颜色组成的3X3矩形，需要使每一行的颜色相同(如图1)，玩家可通过周围的12个按钮来改变顺序。点击靠近按钮的那一行或列即可把这一行或者列所有的颜色往按钮方向移动一格,最顶端的颜色会移动至最末尾，规则就是这样。

为了找到解决此问题的最短步骤，我使用了BFS、两处栈(其实只需一个队列)、一个队列 。

首先要找到最短步骤，显然BFS很适用此问题，一共12个按钮，实际生效的按钮其实只有6个（因为另六个只是反着过来，实际效果就是对应按钮按下n-1次的效果）,所以只需对6个按钮做BFS即可,这里我们取左和上这6个按钮. 

BFS策略:每次读取队列首部,判断此时的状态是否是游戏成功,

• 如果未成功,对此时的6个按钮做枚举,如果按下后的状态没有记录过,则依次入队,并记录入队的颜色状态

• 如果成功,则跳出BFS,此时的结果就是我们想要的结果.这里给出部分代码:

  这里ki=0 ki<3 ki++ 而不是6, 是因为我用了两个for分别枚举的行和列

至此我们已经知道能否找到最短步骤解，但还需要增加一些逻辑来给出最短步骤的每一步。

在存颜色信息的数据结构中增加一个std::stack记为msta,表示至此颜色,已经经过的按钮按下步骤的记录

然后每当找到一个未记录过的颜色信息,就把BFS队列首部的msta加入此时的按钮编号.这样最后得到的颜色信息中就记录了所有的按钮按下顺序.

最后还有一步,就是显示按钮按下顺序,由于我们是用栈存储的记录,最后的一次按钮记录在栈顶,所以需要声明另一个栈,然后依次把栈顶出栈,出栈元素入栈到另一个栈中,这样另一个栈再依次出栈,得到的结果就是顺序的了!

总结:虽然3x3比较简单,可以总结经验来解决,但是如果给一个10x10下的此问题就很棘手了.用程序来解决,不用动脑子,也可以锻炼自己的能力(虽然我10分钟就有正确的思路了(逃