[程序]朴素解法

正弘

160 阅读

发布于 2020-06-25

这个游戏，我们直接去模拟。这里给出我的一份代码，可以用c4droid运行，程序运行后将给出关卡的所有可行解的方案、方案的数量、完成关卡的最小操作步数、最大操作步数。
使用方法如下：
比如27关

我们先在程序中输入
4 3 3
1 1 0
1 1 2
两个数字以空格分开，关卡中的"空格"输入为零0接着我们输入"空格"的行号列号，这里的"空格"在第二行，第三列
2 3
两个数字同样由空格分开。整体如下:

输入法中按下回车，程序就会开始运行，得到结果比如

最下面一行的三个数字分别代表，27关有1342个可行解，完成关卡的最小步数为15步，最大步数为16步。其余行皆为可行方案之一。
比如得到的一个可行解的数列为1 2 3 4 5 6，那怎么使用呢？我们将游戏中的九宫格从左到右，从上到下依次编号为1～9，比如27关中，数字"4"所在格编号为1，数字"2"所在格编号为9，"空格"所在格编号为6。
接着，我们按照数列，依次点击方格1、2、3、4、5、6即可通关。
————————算法时间复杂度分析：
时间复杂度无法直接计算，与游戏的具体情况有关，与九宫格的数字总和成正相关关系。随着数字总和的增大，程序的计算数量将成指数级，乃至阶乘级增长。比如一个可能的游戏(0为空格)
3 4 3
2 4 2
1 0 1
将其AllZero，有275796种可行解，而程序在求解的过程中，则递归了近950万次。
————————考虑可行性剪枝：
那既然有这么多的冗余计算，我们能不能预判一下，提早放弃一些不可能的方案，以减小我们的递归次数？答案是肯定的，但是没有太大的作用。实际上，用我们的游戏经验去优化程序的计算过程，剪枝的代价与直接暴力求解的代价其实相差不大。
cpp