Archive for the ‘算法’ tag
Hunting ghost in a haunted house on a Surface computer
微软117楼一楼有一台Surface计算机，上面有不少multitouch的演示，比如弹钢琴，拼图，live地图等等。其中一个比较有趣的小游戏叫Hunting ghost in a haunted house，就是好多小鬼，每个小鬼都跟另外两个小鬼相连，但是大家的连线互相交叉，游戏目的就是移动小鬼使他们最后变成手拉手一个大环形，不再互相交叉。比如下图最简单有四个小鬼，红色为交叉线段，解决游戏只需要把最左下角的小鬼如图挪到最右边即可。当然有很多解法，这里随便给一个。
游戏给60秒的时间，每关会多一个小鬼，如果一关在某个限定时间内完成的话会给10秒钟的奖励。因为是multitouch，多点触摸，同时可以移动n个小鬼，我跟我的朋友一起玩。游戏一开始很简单，凭直觉随便挪一挪就搞定。但是到后面每增加一个小鬼，难度呈指数级增加，只见满眼的红线，俩人忙的如同没头苍蝇，直接进入panic状态，试了几把都到12只小鬼的时候止步不前了。
跟朋友吃饭的时候很兴奋的讨论着，如果用计算机如何解决这个问题。一上来想到就是用递归去解，很简单，从n个小鬼到n-1个小鬼的解法，3个小鬼就是base case，但是对应的人工并不好实现。朋友甚至异想天开的想用物理模型来模拟，把整个环想成一个大橡皮筋，松手之后每个小鬼都会自动弹回到受力最小的位置，不过更是于事无补了。
吃完午饭突然灵光一现想到一个好办法，不禁狠骂自己这么简单的问题还要想这么半天。今天中午俩人又跑去实践了一把，并对俩人同玩的情况进行了优化，成绩直接提高到20只小鬼，估计再拼一下21只也是可以的。主要因为Surface灵敏度还是不够好，经常挪不动小鬼，而且挪好的小鬼有时候会到处乱跑，有一次甚至跑到屏幕外面，让我俩直接干瞪眼。
那么，到底如何挪小鬼才能做到多快好省呢？
懒人可以等我星期二上班揭晓答案，或者等勤快读者直接贴答案。
下面给一个17个小鬼交叉的示意图：
