[数据结构与算法]POJ - 3279 Fliptile（状态压缩）

POJ - 3279 Fliptile

#include<cstdio>
#include<cstring>
const int N = 20;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

int n, m, ansf = 0;
int g[N][N], b[N][N], ans[N][N];

void turn(int x, int y) //翻转函数
{
	b[x][y] ^= 1;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i], ny = y + dy[i];
		if (~nx && ~ny && nx < n && ny < m) b[nx][ny] ^= 1;
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%d", &g[i][j]);

	for (int i = 0; i < (1 << m); i++) //字典序遍历第一行的翻转
	{
		memcpy(b, g, sizeof g);
		memset(ans, 0, sizeof ans);
		for (int j = 0; j < m; j++)
			if (i >> j & 1)
			{
				turn(0, j);
				ans[0][j] = 1;
			}

		for (int j = 0; j < n - 1; j++)
			for (int k = 0; k < m; k++)
				if (b[j][k])
				{
					turn(j + 1, k);
					ans[j + 1][k] = 1;
				}

		int f = 1;
		for (int j = 0; j < m; j++)
			if (b[n - 1][j]) //存在1表示答案不可行
				f = 0;

		if (f) //如果找到可行答案
		{
			ansf = 1;
			break;
		}
	}
	if (ansf)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
				printf("%d ", ans[i][j]);
			printf("\n");
		}
	}
	else printf("IMPOSSIBLE");

	return 0;
}