[POJ]POJ1753 – Flip Game(递归枚举)

借鉴。

题目地址:http://poj.org/problem?id=1753

参考答案:http://www.cnblogs.com/shuaiwhu/archive/2012/04/27/2474041.html

本题的题意是在一个4 * 4的棋盘中,将棋盘内所有棋子都翻为白色或者全为黑色,则完成任务,如果不存在这种可能性,则输出Impossible。翻转的规则是,每翻动某一枚棋子,则与该棋子同行,同列的棋子也进行翻转。

那么,连续翻转偶数次和翻转0次的效果是一样的,连续翻转奇数次也和翻转1次的效果一样。

于是我们可以发现,翻转的情况是有限个的。最多翻转16个格子,最少翻转0个格子,而翻转的格子不一样。但必然是有限次数。可以使用枚举法,从0个格子一直网上递增到16个格子,如果翻转了所有的16个格子依旧没有得到同色的结果,则返回impossible的结果。

依次选择0个格子,1个格子,2个格子……16个格子。一旦条件满足则找到答案。

也就是说,遍历次数为:

本题是通过看答案才完成的,不过这并不是最优解法。原因是该解法的枚举太过浪费时间了。而题目规模又不大。不过,枚举本来就是耗时间的。本题在POJ上花了950MS,差点就超时了。而下一题POJ2965情况比本题更复杂,用这个解法会超时。

本解法先将要翻的棋子都选好,然后再一次性去翻,最后判定是不是正确答案。而DFS的方法边翻边走,效率比较高。

评论已关闭。