poj 3279 Fliptile 反转开关问题

缘起

日常浪费生命 poj 3279 Fliptile

分析

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
给你一个M*N的棋盘, 上面不是白（0表示）就是黑（1表示）. 翻转一个格子将导致它上下左右相邻的格子也翻转. 
问最少几次能将棋盘全部变成0? 如果办不到的话,输出 IMPOSSIBLE

【输入】
第一行是M,N
1 ≤ M ≤ 15; 1 ≤ N ≤ 15
后面是一个M*N的01矩阵

【输出】
M*N矩阵，每个数字表示此格子翻转的次数. 如果有多种方案的话，输出字典序最小的那个方案.

【样例输入】
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

【样例输出】
0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0

【限制】
2s

其实关于反转开关问题的话，【2】已经做过一道题了. 但是那道题是一维的. 【2】的方法能照搬到此题吗? 不行的~ 因为如果照搬【2】的方法的话，那就首先考虑(1,1)的格子的翻转让其变成白的. 但是能让其变成白的不仅仅可以反转(2,1)亦可以反转(1,2). 所以不能有效降低问题的规模.

那本题和【2】中就没有一点相同之处吗? 非也~ 起码本题满足反转开关问题的两个特点

  1. 一个格子反转2次相当于没反转
  2. 反转的次序不重要.

所以每个格子至多翻转1次. 也就是答案也必定是01矩阵

那本题该怎么解决呢? 记住，二维反转问题要确定的是一维的状态. 所以本题要先确定第一行的反转. 枚举第一行的反转状态（2^N种，注意，并不是说第一行立刻变成白的才是反转方案的. 很可能第一行反转的时候未必都变成0，通过第二行的反转将第一行再变成0，所以第一行的2^N种翻转状态都是可能的,所以才要枚举）.然后只要第一行的反转状态确定了，则后面第二行的反转状态也就确定了，从而第三行也就确定了，直至第M-1行. 然后看看第M行是不是都变成0了. 如果是的话，表明第一行的选择是可行的方案. 否则第一行的选择就不是可行的方案.

而枚举第一行的2^N种翻转方案就是枚举{0,…,N-1}的全部2^n个子集. 这可以参见【1】的二进制状态压缩算法.

至于字典序最小, 因为第一行的翻转一旦确定的话，则后面的翻转就是确定的, 所以只需要保证第一行字典序最小即可. 而我们枚举{0,1,..,n-1}的全部子集就是按照字典序上升的顺序

所以我们可以写下下面的ac代码

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

int m,n, a[20][20],b[20][20],c[20][20],d[20][20], dir[5][2] = {{0,0},{1,0},{-1,0},{0,1},{0,-1}}; // c用于记录每次的翻转方案,d用于记录字典序最小的

void flip(int i, int j) // 模拟反转b[i][j]
{
	for (int x = 0,ni,nj; x<5; x++)
	{
		ni = i+dir[x][0];
		nj = j+dir[x][1];
		if (0<=ni&&ni<m&&0<=nj&&nj<n) // 反转
		{
			b[ni][nj] = !b[ni][nj];
		}
	}
}

int getk(int k) // 返回a[0]的翻转方法的反转次数并且改变周遭的格子
{
	int ans = 0, i = n-1;
	while(~i)
	{
		if (k&1) // 翻转 a[0][i]及周遭
		{
			c[0][i] = 1; // 记录此次第一行的翻转方案
			ans++;
			flip(0,i);
		}
		k>>=1;
		i--;
	}
	return ans;
}

bool ok() // 判断是否可行, 即判断最后一行有没有变成全白
{
	for (int j = 0; j<n;j++)
	{
		if (b[m-1][j])
		{
			return false;
		}
	}
	return true;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &m,&n);
	for (int i = 0; i<m;i++)
	{
		for (int j = 0; j<n;j++)
		{
			scanf("%d", a[i]+j);
		}
	}
	int ans = ~0u>>1;
	for (int k = 0,ret; k<(1<<n); k++) // 枚举第一行的翻转方法. k的低比特位对应第一行右边的格子的翻转方法(这是为了打印字典序最小的最优解)
	{
		memcpy(b,a,sizeof(a)); // b是用来模拟的棋盘
		memset(c, 0, sizeof(c));
		ret = getk(k); // k时, 需要翻转的次数
		for (int i = 1; i<m; i++) // 开始决定a[1,...,m-1]行的翻转方案,每一行翻转方案的决定的目的都是为了上一行变白
		{
			for (int j = 0; j<n;j++) // a[i][j]是否翻转取决于a[i-1][j]的状态
			{
				if (b[i-1][j]) // 如果是黑色的话, 就要翻转了
				{
					c[i][j] = 1; // 记录翻转方案
					ret++; // 此k决定的翻转方案的翻转次数+1
					flip(i,j); // 模拟翻转
				}
			}
		}
		if (ok() && ans>ret) // 只有是真的比之前小的可行方案我才会复制到d中去. 所以这样可以保证是字典序最小的最优解
		{
			ans = ret;
			memcpy(d,c,sizeof(c));
		}
	}
	if (ans!=(~0u>>1))
	{
		for (int i = 0; i<m; i++)
		{
			if (i)
			{
				puts("");
			}
			for (int j = 0; j<n;j++)
			{
				if (j)
				{
					putchar(' ');
				}
				printf("%d",d[i][j]);
			}
		}
	}
	else
	{
		puts("IMPOSSIBLE");
	}
	return 0;
}

ac情况

Status Accepted
Time 438ms
Memory 112kB
Length 1826
Lang C++
Submitted 2019-09-02 12:35:48
Shared
RemoteRunId 20824952

参考

【1】https://yfsyfs.github.io/2019/09/02/%E4%BA%8C%E8%BF%9B%E5%88%B6%E7%8A%B6%E6%80%81%E5%8E%8B%E7%BC%A9/

【2】https://yfsyfs.github.io/2019/09/01/poj-3276-Face-The-Right-Way-%E5%BC%80%E5%85%B3%E9%97%AE%E9%A2%98/