POJ-3279/LG-1985/6201

FJ 知道，智商高的奶牛产奶量也大，所以他为奶牛们准备了一个翻动瓦片的益智游戏。

在一个 $M \times N$ 的方阵上（$1 \leq M,N \leq 15$），每个格子都有一个可以翻转的瓦片。瓦片的一面是黑色，另一面是白色。对一个瓦片翻转，可以让它的颜色由黑到白，或是由白到黑。

然而奶牛们很笨拙，它们翻转一个格子的瓦片时，与其有公共边的所有瓦片也会翻转。

现在奶牛们想知道，至少需要多少次翻转，使所有的瓦片都变成白色朝上呢？

思路

说实话一开始没啥思路这题。

然后看了看评论区，得到了枚举第一行操作的提示。

首先一个显然的性质，每个格子最多被操作一次，两次及以上都是无意义的。

所以可以考虑枚举第一行的操作，共 $2^n$ 种。

第一行的操作被指定后，若其仍有黑色朝上的瓦片，那么一定是对对应列的第二行瓦片操作后使其翻面。如此，第二行的操作也被固定了。

以此类推，可以推出每个格子的操作。

最后判断推完后所有瓦片是否白色朝上即可。

注意题目条件，先要确保翻转次数最少 ，再输出字典序最小的方案。

代码

#include<bits/stdc++.h>
#define INF 0x7fffffff
#define N 20

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int m,n,s[N][N],t[N][N],p[N][N],ans[N][N],cnt=INF,js;

void modify(int x,int y) {
    t[x][y]^=1;
    if(x-1>0) t[x-1][y]^=1;
    if(y-1>0) t[x][y-1]^=1;
    if(y+1<=n) t[x][y+1]^=1;
    if(x+1<=m) t[x+1][y]^=1;
}

void check() {
    if(js>=cnt) return ;
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) if(t[i][j]) return ;
    }
    cnt=js;
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) ans[i][j]=p[i][j];
    }
}

void init() {
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) t[i][j]=s[i][j];
    }
    memset(p,0,sizeof(p));
    js=0;
}

void solve() {
    for(int i=0;i<(1<<n);i++) {
        init();
        int tmp=i;
        for(int j=1;j<=n;j++) {
            p[1][n-j+1]=tmp&1;
            if(tmp&1) {
                js++;
                modify(1,n-j+1);
            }
            tmp>>=1;
        }
        for(int j=2;j<=m;j++) {
            for(int k=1;k<=n;k++) {
                if(t[j-1][k]) {
                    js++;
                    p[j][k]=1;
                    modify(j,k);
                }
            }
        }
        check();
    }
}

int main() {
    m=read(),n=read();
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) s[i][j]=read();
    }

    solve();
    if(cnt!=INF) {
        for(int i=1;i<=m;i++) {
            for(int j=1;j<=n;j++) printf("%d ",ans[i][j]);
            printf("\n");
        }
    }
    else printf("IMPOSSIBLE\n");
    
    system("pause");
    return 0;
}