POJ-2965

题目大意：

有一个4X4的冰箱阵列，当你改变一个冰箱门的状态（开或关），同行同列的冰箱门也会发生改变，给定一个序列，问从全部的冰箱门打开（“-”为开、“+”为关）到给定序列需要几步，以及具体的打开方式。

输入示例：
1
2
3
4
-+--
----
----
-+--
输出示例：
1
2
3
4
5
6
7
6
1 1
1 3
1 4
4 1
4 3
4 4

Solution1（枚举）:

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int m[4][4];
int dx[16],dy[16],ans[16][2];
int ansn = 40;
bool isComplete(){
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(m[i][j] == 1) return false;
        }
    }
    return true;
}

void flip(int i, int j){
    for(int k = 0; k < 4; k++){
        m[k][j] = !m[k][j];
        m[i][k] = !m[i][k];
    }
    //m[i][j]被翻转了两次，再翻转抵消一次。
    m[i][j] = !m[i][j];
}

//d:翻转的次数，s:要翻转的序号
void dfs(int d, int s){
    if(isComplete()){
        ansn = min(ansn,d);
        for(int i = 0; i < ansn; i++){
            ans[i][0] = dx[i];
            ans[i][1] = dy[i];
        }
    }
    if(s >= 16) return;
    dfs(d,s+1);
    flip(s/4,s%4);
    dx[d] = s/4;
    dy[d] = s%4;
    dfs(d+1,s+1);
    flip(s/4,s%4);
    dx[d] = 0;
    dy[d] = 0;
}
int main(){
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            char c;
            scanf("%c",&c);
            m[i][j] = c == '+' ? 1 : 0;
        }
        getchar();
    }
    dfs(0,0);
    printf("%d\\n",ansn);
    for(int i = 0; i < ansn; i++){
        printf("%d %d\\n",ans[i][0]+1,ans[i][1]+1);
    }
    return 0;
}

思路：

直接枚举所有的状态，每个冰箱门都有转换和不转换两种状态，一共有16个冰箱门，所以有2的16次方种状态。
在所有的序列中取一个步数最小的即可。

Solution2（位运算压缩）：

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int dx[16],ans[16];
int ansn = 40;
int state;


void flip(int i, int j){
    for(int k = 0; k < 4; k++){
        state = state ^ (1<< (i*4+k));
        state = state ^ (1 << (k*4+j));
    }
    state = state ^ (1 << (i*4+j));
}

//d:翻转的次数，s:要翻转的序号
void dfs(int d, int s){
    if(!state){
        //更新结果
        ansn = min(ansn,d);
        for(int i = 0; i < ansn; i++){
            ans[i] = dx[i];
        }
    }
    if(s >= 16) return;
    dfs(d,s+1);
    //翻转
    flip(s/4,s%4);
    //保留翻转的位置
    dx[d] = 1 << s;
    dfs(d+1,s+1);
    //回溯
    flip(s/4,s%4);
    dx[d] = 0;
}
int Pos(int a){
    int ans = 0;
    while(a){
        ans++;
        a >>= 1;
    }
    return ans;
}
int main(){
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            char c;
            scanf("%c",&c);
            // m[i][j] = c == '+' ? 1 : 0;
            if(c == '+')
                state = state | (1 << (i*4+j));
        }
        getchar();
    }
    dfs(0,0);
    printf("%d\\n",ansn);
    for(int i = 0; i < ansn; i++){
        int a  = Pos(ans[i])-1;
        printf("%d %d\\n",a/4+1,a%4+1);
    }
    return 0;
}

思路：

在上一题解的基础上，我们发现没有必要用二维数组来存储状态，可以使用一个16位的整数来存储，第几位二进制位表示第几个冰箱的状态。

记录改变冰箱的位置也同样可以使用一个16位的整数来存储。1表示该冰箱门改变了状态，所有的改变不会超过16个，使用16个整数就可以表示全部的移动的过程。

然后更新结果，并提取出来每一位即可。

Solution3（找规律）：

通过找规律我们发现：

  • 一个冰箱门状态改变两次等于不变。

  • 在上一条的基础上，如果以某一冰箱门为基准，将该冰箱门所在的行列上所有的冰箱门都翻转一次，该冰箱门改变，其他冰箱门都不变。

所以我们只要从结果反向推，将每个关闭的冰箱门所在的行列的冰箱门都翻转，更新每个冰箱门的改变的次数，结果状态就为当所有的关闭的冰箱门都被打开后的状态。当次数为奇数说明我们需要改变，偶数则忽略。最后遍历一遍结果数组，取出次数为奇数的冰箱门的坐标即可。

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int record[16][16];

void flip(int i, int j){
    for(int k = 0; k < 4; k++){
        record[i][k]++;
        record[k][j]++;
    }
    record[i][j]--;
}


int main(){
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            char c;
            scanf("%c",&c);
            if(c == '+') flip(i,j);
        }
        getchar();
    }
    
    int cnt = 0;
    for(int i = 0; i <4; i++){
        for(int j = 0; j < 4; j++){
            if(record[i][j]&1) cnt++;
        }
    }
    printf("%d\\n",cnt);
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(record[i][j]&1){
                printf("%d %d\\n",i+1,j+1);
            }
        }
    }
    return 0;
}