POJ——3279 Fliptile

题目大意

给我们一个n×m的矩形格子，上面的值只有1和0，然后我们需要找到一个操作方式（即对哪些格子操作，对哪些格子不操作），将这个操作方式也以n×m的格式输出。使得原本的格子上面的所有数字全部变为0。可能会有很多方式可以得到答案，但是我们要找到第一满足操作数最小，操作数相同的情况下字典序最小的情况。
如果对n×m中的一个点进行操作的话，不仅这个点会反转（即0变成1,1变成0），它周围上下左右4个点也会跟着一起反转。类似小时候玩的黑白棋。
第一行输入行列数，而且其不得超过15。其下是图。

样例输入

4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

样例输出

0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0

题目分析

这题很骚。状态压缩什么的我这种菜鸡暂时不会就按照正常的图来做。第一，因为我们要找到操作数最小的情况，也就是说我们不得不把所有的情况都找上一遍。而最好按字典序顺序从小到大的找，找到一个操作数最小的情况就记下了而若是之后操作数与其相同就不管了因为第一个肯定是字典序最小的。按照这个思路我们应该怎么找？当然，除了第一排之外后面的情况肯定是固定的。当第一排的操作情况固定后，后面的每一排必须要把上一排还没有变成0的位置变成0，而本来就是0的位置一定不能操作。不然到了下下排就不能对上一排操作，答案肯定错误。也就是说要找到正确答案的前提下，当第一排情况固定，基本上整张操作答案图的样子也被固定了。那么我们首先要把所有第一排可能出现的情况列举出来。
因为全是0与1，我们可以联想到二进制（当然这也是别人跟我讲的），例如我们要找到这个样例4×4图形的所有第一排情况，那么我们可以把1<<4，也就是把1左移4，按二进制的思想本来1是00001，将它左移4个，也就变成了10000也就是16。当然右移同理，我们只需要找到0到15也就找到了拥有4列n行的图的第一行的所有情况。例如

0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
9 = 1001
10=1010
11=1011
12=1100
13=1101
14=1110
15=1111

（当然这里是给我这种不是很懂二进制的菜鸡看的）
这样的话不仅把第一行的所有情况找出来了并且还是按照字典序从小到大排列的。
在找到第一行之后剩下的几行就按照规则一一列举出来就好了。这其中还有些骚写法，在代码中能体现出来。
打个比方如何把5=0101以二进制的形式将0101一一取出来。这时候只需要开个循环，执行4步(0<=j<4)，每一步如此：

5>>0 = 0101，然后&1。（意思就是二进制最后一位为1，返回1，否则返回0）
5>>1 = 0010，&1。
5>>2 = 0001，&1。
5>>3 = 0000，&1。
倒着看最后一位的话，这样就将0101取出来了。

代码如下

#include<cstdio>
#include<cstring>
using namespace std;
int vis[20][20],test[20][20],ans[20][20],save[20][20];   //vis用来保存最原始的图，test用来当测试图。ans保存最终答案，save测试答案是否满足条件。
int r,c;
int dx[5]= {1,0,0,0,-1} , dy[5]= {0,1,-1,0,0};

int cont()                           //计数：计算save中有多少次操作也就是多少个1。
{
    int cc=0;
    for(int i = 0 ; i < r; i++)
        for(int j = 0 ; j < c ; j++)
            if(save[i][j]==1) cc++;
    return cc;
}
                                     
void cop()                           //把test这个图又重新复原成原来的图。
{
    for(int i = 0 ; i < r ; i++)
        for(int j = 0 ; j < c ; j++)
            test[i][j] = vis[i][j];
}

int judge()                          //判断test图是否全部变成了0。
{
    for(int i = 0 ; i < r ; i++)
        for(int j = 0 ; j < c ; j++)
            if(test[i][j] != 0) return false;
    return true;
}

bool cheak(int x,int y)              //判断点x,y是否在图形内没有越界（为下个函数做准备）
{
    if(x >= 0 && x < r && y >= 0 && y < c) return true;
    return false;
}

void ope(int x, int y)               //对x,y这个点进行操作。
{
    for(int i = 0 ; i < 5 ; i++)
    {
        int tx = x+dx[i], ty = y+dy[i];
        if(cheak[tx][ty]) test[tx][ty] = !test[tx][ty];
    }
}

int main()
{
    scanf("%d%d",&r,&c);
    for(int i = 0 ; i < r ; i++)                 //读图
        for(int j = 0 ; j < c ; j++)
            scanf("%d",&vis[i][j]);

    bool flag = false;                          //立个flag表示一开始没有满足条件的ans图。
    int cnt = 10000;
    for(int i = 0 ; i < (1<<c) ; i++)
    {
        cop();       // 将test又变回原来的vis初始图。
        memset(save,0,sizeof(save));
        for(int j = 0; j < c ; j++)          // 向save第一行赋值。
            save[0][c-j-1] = (i>>j)&1;
        for(int j = 0 ; j < r - 1 ; j++)
        {
            for(int k = 0 ; k < c ; k++)
            {
                if(save[j][k]==1)
                    ope(j,k);    // 操作test。
            }
            for(int k = 0 ; k < c ; k++)
                if(test[j][k]==1) save[j+1][k] = 1; //将save按照test上一行的规则赋值使其上一行全为0.
        }
        for(int j = 0 ; j < c ; j++)
            if(save[r-1][j]==1)  ope(r-1,j); // 对最后一行进行操作。
        if(judge())
        {
            int now = cont(); // 对save里的操作数进行计数。
            if(now < cnt) //若操作数比之前的小则用save覆盖ans。
            {
                memcpy(ans,save,sizeof(ans));
                cnt = now;
            }
            flag = true;
        }

    }
    if(flag)
    {
        for(int i = 0 ; i < r ; i++)
        {
            for(int j = 0 ; j < c ; j++)
                printf("%d ",ans[i][j]);
            printf("\n");
        }
    }
    else printf("IMPOSSIBLE\n");
}

这篇废话有点多，主要是对我自己而言。