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;
}