POJ3279 Fliptile

题目链接

题意：点击一个点，则这个点和上下左右共五个点都会翻转。问最少点几个点可以使地图全是 0。

思路：枚举第一行所有可能的情况，第一行若有 1 的话必须翻转下一行对应位置才可以满足条件，以此类推，最后判断最后一行是否满足条件。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
int m, n;
int pic[20][20];
int flip[20][20];  //当前解
int ans[20][20];  //最优解
int dir[5][2]{-1, 0, 1, 0, 0, 0, 0, 1, 0, -1}; //五个点
int judge(int x, int y){    //通过这个点被翻动的次数判断这个点是否为黑
    int a = pic[x][y];
    for(int i = 0; i < 5; i++){
        int x1 = x + dir[i][0];
        int y1 = y + dir[i][1];
        if(x1 >= 0 && y1 >= 0 && x1 <m && y1 < n)
            a += flip[x1][y1];
    }
    return a&1;
}
int cal(){
    for(int i = 1; i < m; i++){
        for(int j = 0; j < n; j++){
            if(judge(i-1, j))       //如果这个点是1
                flip[i][j] = 1;     //翻转这个点下一行对应的点
        }
    }

    for(int i = 0; i < n; i++)      //验证最后一行是否满足条件
        if(judge(m-1, i))
            return 0x7fffffff;

    int cnt = 0;                    //本次情况的翻转次数cnt
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
            if(flip[i][j])
                cnt++;
    return cnt;
}
int main(){
    //freopen("a.txt", "r", stdin);
    while(scanf("%d %d", &m, &n) != EOF){
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                scanf("%d", &pic[i][j]);
        int cnt = 0x7fffffff;

        for(int i = 0; i < (1<<n); i++){   //第一行共2^n种情况
            memset(flip, 0, sizeof(flip));
            for(int j = 0; j < n; j++)
                flip[0][j] = (i>>j)&1;  //每种情况中，第一行的n个数
            int temp = cal();           //求解这种情况的答案
            if(temp < cnt){             //比较
                cnt = temp;
                for(int i = 0; i < m; i++)
                    for(int j = 0; j < n; j++)
                        ans[i][j] = flip[i][j];
            }
        }
        if(cnt == 0x7fffffff)
            cout << "IMPOSSIBLE" << endl;
        else{
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(j) cout << " ";
                    cout << ans[i][j];
                }
                cout <<endl;
            }

        }
    }
    return 0;
}