忧郁樱桃

文章
6
资源
0
加入时间
3年2月3天

UVa 1343 The Rotation Game 旋转游戏 IDA* BFS 路径还原

算法,直接依次枚举进行的操作(需要注意的是,应该先枚举字典序小的),很明显可以发现,每一次移动最多只会让中间的位置正确的数字个数增加一,所以可以考虑的剪枝是:最大深度与当前深度之差如果小于中间最少的不对的数字时进行剪枝。来解决本题的时候,我们可以转换一下思路,我们可以把目标状态能够到达的所有其他状态枚举出来,这样的花费与从某个状态到目标状态是一样的。操作如何进行,其他的操作如何进行可以类似的推出,你的任务是找到最少的操作步数让中间的八个数字为同一个数字,例如上图左边经过两次操作能将中间全部变成。