POJ 2965 The Pilots Brothers' refrigerator【BFS+状压 Or 脑洞】

题目链接：

题意：

给定冰箱门的开关情况，改变一个门则其所在行列的门都会发生改变，求出改变门的最少操作使得最终所有门都是打开状态。

代码：

bfs+状态压缩很容易想到~~

这里的状态压缩要需要多加小心，注意一下存储的是翻转门的情况~

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

typedef pair<int, int> p;

const int maxn = 1<<17;

struct node

{

    int value;

    int step;

};

int pos[maxn];

int vis[maxn];

int x[maxn], y[maxn];

node sta;

int pa[maxn];

int dir[16] = {

    0xf888, 0x8f88, 0x88f8, 0x888f, 0xf444, 0x4f44, 0x44f4, 0x444f,

    0xf222, 0x2f22, 0x22f2, 0x222f, 0xf111, 0x1f11, 0x11f1, 0x111f

};

int bfs()

{

    queue<node>q;

    vis[sta.value] = 1;

    sta.step = 0;

    pa[sta.value] = -1;

    q.push(sta);

    while(!q.empty()){

        node t = q.front();q.pop();

        if(!t.value)  return t.step;

        for(int i = 0; i < 16; i++){

            node n;

            n.value = t.value ^ dir[i];

            if(vis[n.value]) continue;

            vis[n.value] = 1;

            pa[n.value] = t.value;

            n.step = t.step + 1;

            pos[n.value] = i;

            q.push(n);

         }

    }

    return -1;

}

int main (void)

{

    char c;

    for(int i = 0; i < 4; i++){

        for(int j = 0; j < 4; j++){

            scanf("%c",&c);

            if(c== '+') sta.value |= 1<<(15- i * 4 - j);

        }

        getchar();

    }

    int res = bfs();

    int va = 0;

    for(int i = 0; i < res; i++){

         x[i] = pos[va] % 4 + 1;

         y[i] = pos[va] /4 + 1;

         va = pa[va];

    }

    printf("%d\n",res);

    for(int i = res - 1; i >= 0; i--)

        printf("%d %d\n", x[i], y[i]);

    return 0;

}

分析：

脑洞做法：

首先观察样例，发现关门的在(1,2)(4,2)，而样例却把他们所在行和列的全部翻了一遍。试想，对于某一点(1,2)来说，行和列的元素都翻一遍的话， (1,2)改变了7次，行列元素改变4次，而其他元素改变2次~~也就是说实际上只有(1,2)的状态改变了。把所有行列的元素翻一遍，记录翻动次数，统计翻转过后依然不满足的有多少个，直接翻转这些就好了~至于这道题因为(1,2)(4,2)本身在同一列~所以最后翻动次数为偶数~相当于没有动，就可以不翻转他们了~

#include<iostream>

using namespace std;

const int maxn = 10;

int a[maxn][maxn];

int m[maxn][maxn];

int row[maxn], cal[maxn];

int main (void)

{

    char c;

    for(int i = 0; i < 4; i++){

        for(int j = 0; j < 4; j++){

            cin>>c;

            a[i][j] = (c=='-')?0:1;

        }

    }

    for(int i = 0; i <4 ;i++){

        for(int j = 0; j < 4; j++){

            if(!a[i][j]) continue;

            for(int k = 0; k < 4; k++){

                m[i][k]++;

                m[k][j]++;

            }

        }

    }

    int res = 0;

    for(int i = 0; i < 4; i++){

        for(int j = 0; j < 4; j++){

            if((m[i][j] + a[i][j])&1){

                row[res] = i;

                cal[res++] = j;

            }

        }

    }

    cout<<res<<endl;

    for(int i = 0; i < res; i++)

        cout<<row[i] + 1<<' '<<cal[i] + 1<<endl;

    return 0;

}

这种方格上玩一个方块动会对周围的方块产生影响之类的问题，适合用奇偶表示翻转状态~~~

遇见问题还是要多思考多观察~~不要硬碰硬，说不定会有更巧妙的方法~