费解的开关

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

我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

1
2
3
4
5
10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

1
2
3
4
5
01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

1
2
3
4
5
01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
输入格式

第一行输入正整数n，代表数据中共有n个待解决的游戏初始状态。

以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
输出格式

一共输出n行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出“-1”。

数据范围：0<n≤500

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例：

1
2
3
3
2
-1

Solution1（TLE）：

我们可以枚举每个开关的状态，然后查看是否全亮，每个开关两个状态（开和关），一共有25个开关，所以复杂度为O(2^25) = 33554432次。

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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int m;
int ans = 26;
void flip(int k){
    int i = k / 5,j = k % 5;
    m ^= 1 << k;
    if(j-1 >= 0) m ^= (1 << (i * 5 + (j-1)));
    if(j+1 < 5) m ^= (1 << (i *5 + (j+1)));
    if(i-1 >= 0) m ^= (1 << ((i-1) *5 + j));
    if(i+1 < 5) m ^= (1 << ((i+1) *5 + j));
}

void dfs(int k,int d){
    if(m == (1<<25)-1){
        ans = min(ans,d);
        return;
    }
    if(k >= 26) return;
    dfs(k+1,d);
    flip(k);
    dfs(k+1,d+1);
    flip(k);
}

int main(){
    freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    getchar();
    while(T--){
        char c[10];
        m = 0;
        ans = 26;
        for(int i = 0; i < 5; i++){
            scanf("%s",c);
            for(int j = 0; j < 5; j++){
                if(c[j] == '1') m |= (1 << (i*5+j));
            }
            printf("%s\\n",c);
            getchar();
        }
        printf("%#x\\n",m);
        dfs(0,0);
        if(ans > 6) ans = -1;
        printf("%d\\n",ans);
    }
    
    return 0;
}

Solution2：

我们可以从行的角度来看：
如果当前行确定了，我们要让所有的开关打开，就要选把当前行中关闭的灯的下面位置的切换状态。
归纳到一般情况，当第一行的状态确定了，我们为了使所有的开关打开，去下一行改变状态，使得当前行的所有灯打开。如此4次后，由于到达了最后一行，这时，我们检查最后一行的灯是否全部亮，（前面4行已经全部亮了）。如果全亮，则当前的选择为一个可选方案，这时更新翻转的次数。

复杂度为O(n * 2^5)。

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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;

char m[10][10];
int ans = INF;
int dx[5] = {0,-1,0,1,0};
int dy[5] = {0,0,1,0,-1};
void flip(int x,int y){
    for(int i = 0; i <5; i++){
        int xi = x + dx[i];
        int yi = y + dy[i];
        if(xi >= 0 && xi < 5 && yi >= 0 && yi < 5){
            m[xi][yi] ^= 1;
        }
    }
}

void solve(){
    char backup[10][10];
    int res = 0;
    memcpy(backup,m,sizeof(m));
    for(int i = 0; i < 1 << 5; i++){
        res = 0;
        for(int j = 0; j < 5; j++){
            if(i >> j & 1){
                res++;
                flip(0,j);
            }
        }
        for(int j = 0; j < 4; j++){
            for(int k = 0; k < 5; k++){
                if(m[j][k] == '0'){
                    flip(j+1,k);
                    res++;
                }
            }
        }
        bool flag = true;
        for(int j = 0; j < 5; j++){
            if(m[4][j] == '0'){
                flag = false;
                break;
            }
        }
        if(flag) ans = min(ans,res);
        memcpy(m,backup,sizeof(backup));    
    }

}

int main(){
    // freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    getchar();
    while(T--){
        ans = INF;
        for(int i = 0; i < 5; i++){
            scanf("%s",m[i]);
            // printf("%s\\n",m[i]);
        }
        solve();
        if(ans > 6) ans = -1;
        printf("%d\\n",ans);
    }

    return 0;
}