【POJ】[3279]Fliptile - BoilTask's Blog

问题描述

问题分析

比较难想的一题，但是这也是很经典的一题
经典游戏“点亮灯泡”就是这种
也就是按下一个开关，这盏灯及上下左右的灯会改变状态
因为一个开关按两次是没有意义的
所以对于每个开关只有两种状态
按或者不按所以这一题就是要求输出
每一个开关按(1)或者不按(0)

题目问是否能通过操作让所有的1变成0
如果不能则输出IMPOSSIBLE
如果有多种操作则输出需要按(1)的次数最少的
如果次数相等则输出结果字典序最小的那个
(如果有00111和11100则输出00111)

思路：
若枚举所有格子开或不开有$2^{n*m}$个状态
所以在1≤M≤15,1≤N≤15的范围内肯定是要爆炸
所以思考能否优化

事实上，若第一行确定，则它的下一行的点法必然是确定的
因为对第一行有影响的只有第二行它对应的灯
所以若第一行灯没亮则第二行应该要按下开关使它点亮
以此类推可得所有的状态
如果最后一行在按完之后也全部点亮
则说明这种方案是成立的
所以可以枚举第一行的操作有$2^m$个状态

代码：
为了方便表示出第一行灯的操作
可以使用二进制来表示是否操作

1
2
3
4
0000(0) 表示 否否否否
0001(1) 表示 否否否是
0010(2) 表示 否否是否
0011(3) 表示 否否是是

以此类推即可用循环把所有操作表示出来
共有$2^m$次循环
对于每一个i可以进行且操作i&1为二进制最后一位数
而对于判断灯亮灭则可使用异或操作
因为我们有运算法则

1
2
3
4
0^1==1
1^1==0
0^0==0
1^0==1

也就是异或1则改变异或0则不变
这与灯是否被操作的情况是相同的

得到每种状态第一行的操作后
我们可以依次向下判断来更新答案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<stdio.h>
#include<string.h>
int map[20][20];
int temp[20][20];
int N,M;
void Pr(int x) {
    for(int i=0; i<M; i++) {
        map[0][i] ^= (x>>(M-1-i))&1;
        if((x>>(M-1-i))&1) {
            if(i>0)
                map[0][i-1] ^= 1;
            if(i<M-1)
                map[0][i+1] ^= 1;
            if(N>1)
                map[1][i] ^= 1;
        }
        printf("%d",(x>>(M-1-i))&1);
        printf("%c",i==M-1?'\n':' ');
    }
    for(int i=1; i<N; i++) {
        for(int j=0; j<M; j++) {
            printf("%d",map[i-1][j]);
            if(map[i-1][j]==1) {
                map[i-1][j] ^= 1;
                map[i][j] ^= 1;
                if(j>0)
                    map[i][j-1] ^= 1;
                if(j<M-1)
                    map[i][j+1] ^= 1;
                if(i<N-1)
                    map[i+1][j] ^= 1;
            }
            printf("%c",j==M-1?'\n':' ');
        }
    }
}
int main() {
    while(scanf("%d %d",&N,&M)!=EOF) {
        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++)
                scanf("%d",&map[i][j]);
        int res=99999999,rest=-1;
        int T=(1<<M),max=T-1;
        while(T--) {
            memcpy(temp,map,sizeof(map));
            int t=T^max;
            int cnt=0;
            for(int i=0; i<M; i++) {
                temp[0][i] ^= (t>>(M-1-i))&1;
                if((t>>(M-1-i))&1) {
                    cnt++;
                    if(i>0)
                        temp[0][i-1] ^= 1;
                    if(i<M-1)
                        temp[0][i+1] ^= 1;
                    if(N>1)
                        temp[1][i] ^= 1;
                }
            }
            for(int i=1; i<N; i++) {
                for(int j=0; j<M; j++) {
                    if(temp[i-1][j]==1) {
                        cnt++;
                        temp[i-1][j] ^= 1;
                        temp[i][j] ^= 1;
                        if(j>0)
                            temp[i][j-1] ^= 1;
                        if(j<M-1)
                            temp[i][j+1] ^= 1;
                        if(i<N-1)
                            temp[i+1][j] ^= 1;
                    }
                }
            }
            int i;
            for(i=0; i<M; i++)
                if(temp[N-1][i]==1)
                    break;
            if(i==M&&cnt<res)
                res=cnt,rest=t;
        }
        if(res==99999999)
            printf("IMPOSSIBLE\n");
        else
            Pr(rest);
    }
    return 0;
}