POJ 2965 The Pilots Brothers' refrigerator

发表于 更新于 分类于 本文字数： 2k 阅读时长 ≈ 2 分钟

本文为POJ 2965 The Pilots Brothers' refrigerator题解。

POJ-2965链接

大意冰箱门上有4*4的手柄，手柄有开和关两种状态，每次可以选择一个手柄将其和所在的行列全部翻转，问最少几次能打开。

题目和POJ 1753很像。

首先分析状态，4*4的手柄，估计状态不会很多，同时对于一个手柄，翻转奇数次或者偶数次的情况是一样的，要么翻一次，要么不翻。

所以最多需要翻转的次数是16次，从1次到16次，一共有

\[ \dbinom{1}{16}+ \dbinom{2}{16}+...+ \dbinom{15}{16}+ \dbinom{16}{16} = 2^{16} \]

同时，我们可以只用一个数字来记录当前冰箱门的状态，每个手柄非开即关，可以用0、1来表示，冰箱门状态可以被一个16位的二进制数代替。

算法大致思路，首先枚举翻转的次数，从1开始。然后在从冰箱门左上角往右下角进行DFS搜索，如果当前手柄要翻转，则把该当前状态二进制数与该手柄对应的二进制位进行异或。到达条件是冰箱门是否为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
#include <cstdio>
using namespace std;
const int dpos[] = {-4, -1, 1, 4};
int ans = 0, num = 0;
int a[6][6], as = 0;
int des[20];

void init()
{
    char ch;
    int res = 0;
    for (int i = 1; i <= 4; i++)
    {
	for (int j = 1; j <= 4; j++)
	{
	    scanf("%c", &ch);
	    if (ch == '+')   a[i][j] = 1, res++;
	    else a[i][j] = 0;
	    num = (num<<1)+a[i][j];
	}
	scanf("\n");
    }
    if (res == 0)  ans = -1;
}

int search(int now, int pos, int cnt)
{
    int flag = 0;
    int nxt = now;
    int x = (pos-1)/4+1, y = (pos-1)%4+1;
    if (cnt == 0)
    {
		if (now == 0)
	    	return 1;
		return 0;
    }
    if (pos + cnt > 17 || pos > 16)  return 0;
    for (int i = 1; i < 4; i++)
    {
		if (x+i<=4)  nxt ^= (1<<(16-((x+i-1)*4+y)));
		if (x-i>=1)  nxt ^= (1<<(16-((x-i-1)*4+y)));
		if (y+i<=4)  nxt ^= (1<<(16-((x-1)*4+y+i)));
		if (y-i>=1)  nxt ^= (1<<(16-((x-1)*4+y-i)));
    }
    nxt ^= (1<<(16-pos));
    flag = search(nxt, pos+1, cnt-1);
    if (flag == 1)
    {
		des[++as] = pos;
		return 1;
    }
    flag = search(now, pos+1, cnt);
    return flag;
}

void work()
{
    int cnt;
    if (ans == -1)
		return (void) printf("0\n");
    ans = 0;
    for (cnt = 1; cnt <= 16; cnt++)
    {
		ans = search(num, 1, cnt);
		if (ans != 0)  break;
    }
    if (ans == 0)  printf("Impossible\n");
    else printf("%d\n", cnt);
    for (int i = as; i >= 1; i--)
    {
		int x = (des[i]-1)/4+1, y = (des[i]-1)%4+1;
		printf("%d %d\n", x, y);
    }
}

int main()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    init();
    work();
    return 0;
}