大体题意：一个冰箱上有4*4共16个开关，改变任意一个开关的状态（即开变成关，关变成开）时，此开关的同一行、同一列所有的开关都会自动改变状态。要想打开冰箱，要所有开关全部打开才行。 输入：一个4×4的矩阵，+表示关闭，-表示打开； 输出：使冰箱打开所需要执行的最少操作次数，以及所操作的开关坐标。

 

最开始自己是状压bfs+队列+模拟取反，然后T了。看了博客，大佬是各种优化，数组模拟队列+预处理异或值。

我用这种方法就A了，我把数组模拟队列+模拟取反，结果刚刚1000ms卡过。233333333333333333

正解还可以用高斯消元，我会高斯消元的模板，以后再更新高斯消元的做法。

 

///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<set>
#include<stack>
#include<map>
#include<new>
#include<vector>
#define MT(a,b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai=acos(-1.0);
const double E=2.718281828459;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;

bool vis[700000];

int flip[4][4]={63624,62532,61986,61713,    ///预处理的异或值
36744,20292,12066,7953,
35064,17652,8946,4593,
34959,17487,8751,4383};

struct node
{
    int status;
    int x;
    int y;
    int pre;
}q[1<<16];

int main()
{
    int num=0,top=0,up=1,n;
    char x;
    for(int i=4; i>=1; i--)
    {
        for(int j=1; j<=4; j++)
        {
            cin>>x;
            n=x=='-'?0:1;
            num=num+(n<<(i*4-j));
        }
    }
    q[++top]=node{num,-1,-1,-1};
    while(1)
    {
        if(q[top].status==0)
            break;
        for(int i=1; i<=4; i++)
        {
            for(int j=1; j<=4; j++)
            {
                int s=q[top].status^flip[i-1][j-1];     ///更新状态
                if(!vis[s])
                {
                    vis[s]=1;
                    q[++up]=node{s,i,j,top};
                }
            }
        }
        top++;
    }
    stack<pair<int,int> >ans;
    while(q[top].pre!=-1)       ///回溯路径
    {
        ans.push(make_pair(q[top].x,q[top].y));
        top=q[top].pre;
    }
    printf("%d\n",ans.size());
    while(!ans.empty())
    {
        printf("%d %d\n",ans.top().first,ans.top().second);
        ans.pop();
    }
    return 0;
}