一笔画游戏

| Comments

在android上看过一个一笔画的小游戏,规则很简单,要连续一笔,不能重复。 当然,到后面比较难的时候还会限制方向,有些线路必须走多次等等。并不是觉得这有游戏做得多么的好,或者很有创意。 我只是从程序员的角度来看问题,用程序是怎么处理的。 我们只需要尝试所有可能的路径就可以了,这里用了回朔法,是一种优化过的穷举,

先来考虑一下数据结构。我们给所有的点加上编号1-n,所有的连线可以用二维数组表示a[n+1][n+1],值为0表示不可联通, 其他表示需要经过的次数(我实现的时候是采用类似稀疏矩阵的链表表示)。
至于给矩阵增加多一列,主要是考虑处理方便,还考虑到起始点不好确定,所以加个虚拟点,
同时增加虚拟点到其他n个点的连接,这样我们深度遍历的时候从虚拟点开始就可以了。
另外我们需要一个链表来存放走过的路径,还需要一个标记来表示找到路径,无需继续尝试。

初始化的伪代码如下,

(0..n).each do |k| a[0][k]=1 end #虚拟点
@path = [] # 走过的路径
@ok=false # 标记是否完成

接下去我们需要一个回溯算法(参考数独(sudoku)游戏),代码比较简单,这里就不展示代码示例了。

需要注意的是,找到一个可走的路径时(例如从i到j,a[i][j]>0),深度遍历的时候需要对这个值减1,回溯的时候加1就可以了。 而对于走过的路径path,是否需要回退呢? 其实我们关心的是把刚刚走过的路径加入路径的正确位置, 如果选择数组的话,在回溯的时候就不可以不回退了,而对于链表,回退则是必要的。

总体来说,这个游戏的实现是比较简单的,有兴趣的同学可以自己实现一下。

Comments