费解的开关(二进制状态压缩)

费解的开关

  • 你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
    我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯

自然想到从第一行开始点，但是点第1行第2个时候发现第1个又变了，只能枚举第1行的所有操作，（每点2个决策，5个点，有 $2^5$次操作），然后去点击题目给的图，

到第2行发现第一行有的点不为1，所以只能点击该点下面一点（一直递推到最后一行，发现其实第一行定了，后面的结果都定了，因为每一点一定要为1）

统计最后一行是否都为1，是的就更新minstep,

状态压缩

  • 压缩的是操作，不是点亮的状态，
    第一行每个点 点亮或者不点 用1,0代替，如 2(00010)点亮第4盏灯,

细节

  • 备份一个原数组
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
#include<iostream>
using namespace std;
char ch[6][6];
char backup[6][6];
int next1[5][2]={0,0,0,1,1,0,0,-1,-1,0};
void click(int x,int y){
    for(int i=0;i<5;i++){
        int tx=x+next1[i][0];
        int ty=y+next1[i][1];
        if( tx>=1 && ty>=1 && tx<=5 && ty<=5)   ch[tx][ty]^=1;
    }
}
int main(){
//    freopen("a.txt","r",stdin);
    int t;
    cin>>t;
    getchar();
    while(t--){
        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++){
                ch[i][j]=getchar();
            }
            getchar();
        }
        getchar();//一个空行
        for(int i=1;i<=5;i++)
            for(int j=1;j<=5;j++)   backup[i][j]=ch[i][j];
        int ans=0x3f3f3f3f;
        for(int states=0;states<(1<<5);states++){
            int step=0;
            for(int j=4;j>=0;j--){
                if( (states>>j) & 1 ){
                    click(1,5-j);
                    step++;
                }
            }
            for(int i=2;i<=5;i++){
                for(int j=1;j<=5;j++){
                    if( ch[i-1][j] == '0'){
                        step++;
                        click(i,j);
                    }
                }
            }
            int j=1;
            for(;j<=5;j++){
                if(ch[5][j] == '0') break;
            }
            if( j == 6 )    ans=min(ans,step);
            for(int i=1;i<=5;i++)
                for(int j=1;j<=5;j++)   ch[i][j]=backup[i][j];
        }
        if(ans<=6) cout<<ans<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}