Zhao70's Blog

POJ3279 Fliptile

发表于 | 分类于

题目大意

给定一个矩阵， 其中有 0 和 1. 每次旋转可以将 0 变为 1, 将 1 变为 0. 但每次旋转一个方块时, 所有邻接的方块都会被旋转, 求字典序最小的旋转方式.

思路

若给定第一行的旋转排列, 便可以得到整个矩阵的旋转方式. 矩阵最大为15 × 15 的标准, 因此可以使用状态压缩第一行, 求出剩下行数的旋转次数与方式, 并进行保存.

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX = 20;
int nRow, nCol;
int tile[MAX][MAX];
int flip[MAX][MAX];
int opt[MAX][MAX];
int d[][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {0, 0}};
int getColor(int x, int y) {
	int cnt = tile[x][y];
	for (int i = 0; i < 5; i++) {
		int x1 = x + d[i][0];
		int y1 = y + d[i][1];
		if(x1 >= 0 && x1 < nRow && y1 >= 0 && y1 < nCol)
			cnt += flip[x1][y1];
	}
	return cnt % 2;
}
int cntF() {
	for (int i = 0; i < nRow - 1; i++) {
		for (int j = 0; j < nCol; j++) {
			if (getColor(i, j) == 1) {
				flip[i + 1][j] = 1;
			}
		}
	}
	for (int j = 0; j < nCol; j++) {
		if (getColor(nRow - 1, j) == 1)
			return -1;
	}
	int cnt = 0;
	for (int i = 0; i < nRow; i++) {
		for (int j = 0; j < nCol; j++) {
			cnt += flip[i][j];
		}
	}
	return cnt;
}
int solve() {
	int res = -1;
	for (int i = 0; i < (1 << nCol); ++i) {
		memset(flip, 0, sizeof(flip));
		for (int j = 0; j < nCol; ++j) {
			flip[0][nCol - 1 - j] = (i >> j) & 1;
		}
		int temp = cntF();
		if ((temp >= 0) && (res == -1 || res > temp)) {
			res = temp;
			memcpy(opt, flip, sizeof(flip));
		}
	}
	return res;
}
int main() {
	cin >> nRow >> nCol;
	for (int i = 0; i < nRow; i++)
		for (int j = 0; j < nCol; j++)
			cin >> tile[i][j];
	if (solve() == -1) {
		cout << "IMPOSSIBLE";
	}
	else {
		for (int i = 0; i < nRow; ++i)
			for (int j = 0; j < nCol; ++j)
				printf("%d%c", opt[i][j], j == nCol - 1 ? '\n' : ' '); 
	}
//	system("pause");
	return 0;
}