poj 3279 Fliptile (搜索..暴力?)

http://poj.org/problem?id=3279

反转类问题.

有N*M个方格,每个上面有数字0或者1

操作一个方格,这个方格即其相邻的四个方格(有公共边)会改变状态(由0变1或者由1变0)

问至少需要多少次操作,所有的状态都为0

如果有多组,输出字典序小的那一组.

跟开关灯的那题相似.

因为每个开关灯的动作还影响其他相邻灯的状态.所以对于这种题,一般思路是,先定住一部分,再由已知定住的这部分去确定其他部分.

对于这道题而言

首先我们可以很容易发现,操作数为偶数和为0是等价的.

操作数为1和为奇数是等价的.

对于这道题而言,我们可以首先枚举第一行的状态,一共有 2<

然后如果 a[i-1][j]为1,因为i-1行的状态已经确定,无法改变,所以能影响到a[i-1][j]的只有a[i][j]

那么a[i][j]一定要操作一次

最后判断最后一行是否都为0,如果为0,表示这种情况是合法的

然后找到操作数最小的一组.

字典序的话,只要是枚举的时候按照数的大小顺序就可以保证.

学会了用memcpy函数.

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz