Fliptile POJ - 3279（枚举）

Fliptile POJ - 3279

题目传送门

题目描述：

在一个m*n的图上，1代表黑色，0代表白色。
奶牛可以翻开瓷砖，当翻开一张白色的瓷砖时，它就变成了黑色；当翻开一张黑色的瓷砖时，它就变成了白色。当奶牛翻开一块瓷砖时，也会连带相邻的瓷砖一起翻转（上下左右）。奶牛需要用最少的翻转次数，将所有瓷砖翻成白色。如果能完成任务，则输出每个点翻转的次数，否则输出”IMPOSSIBLE“。

思路：

翻转次数要最少，所以每个点要么翻转，要么不翻转，对一个点翻转多次（又回到了曾经出现过的状态）。那么输出的应该是0或1（如果能完成任务的话）。
很明显，我们选择的翻转策略应该是：如果当前点（x,y）上一行的点（x+1,y）瓷砖颜色为1，则翻转之。所以，当前点（x,y）需不需要翻转，只取决于(x+1,y)是否为1，而不需要考虑当前点的状态。
也就是说，如果我们确定了第一行的状态，那么后续的图就能确定下来。
接下来只需要枚举出第一行的所有状态，然后拿当前状态去跑DFS，问题得解。

Code：

int n, m;
int map[20][20], M[20][20], e[20][20], v[20][20];
void change(int x, int y) { //如果不越界，翻转之
	map[x][y] ^= 1;
	if (x+1>=1&&x+1<=n)
		map[x+1][y] ^= 1;
	if (y+1>=1&&y+1<=m)
		map[x][y+1] ^= 1;
	if (x-1>=1&&x-1<=n)
		map[x-1][y] ^= 1;
	if (y-1>=1&&y-1<=m)
		map[x][y-1] ^= 1;
}

int solve() {
	int ans = 0;
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (map[i-1][j] == 1) {
				change(i, j);
				ans++;
				v[i][j] = 1;
			}
		}
	}
	// 经过所有翻转后，如果还存在黑色，则不能完成任务
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (map[i][j] == 1) {
				return INF;
			}
		}
	return ans;
}

int main() {
	int minn = INF;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> M[i][j];
	for (int i = 0; i < 1<<m; i++) {
		//M作为模板，每次将M复制入map中，在操作时只改变map即可
		memcpy(map, M, sizeof(map)); 
		memset(v, 0, sizeof(v));
		// tmp为第一行的状态
		int tmp[15], ans = 0;
		for (int j = 1; j <= m; j++) { //二进制枚举状态
			tmp[m-j+1] = i >> (j-1) & 1;
			if (tmp[m-j+1] != M[1][m-j+1]) {
				ans++;
				change(1, m-j+1);
				v[1][m-j+1] = 1;
			}
		}
		ans += solve();
		if (ans < minn) {
			minn = ans;
			memcpy(e, v, sizeof(e));
		}
	}
	if (minn >= INF) cout << "IMPOSSIBLE" << endl;
	else {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cout << e[i][j] << ' ';
			}
			cout << endl;
		}
	}
	return 0;
}