题目链接：

题意：

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

代码：

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

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

#include
     
      #include
      
       #include
       
        using namespace std;typedef pair
        
          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
         
          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
     
      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<
      
       <
      
     

---

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

---

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