题意：有个4*4的开关，里面有着16个小开关
-+--
----
---- '+'表示开关是关着的，'-'表示开关是开着的，只有所有的开关全被打开，总开关才会被打开。现在有一种操作，只要改变某个开关，那么这个开关的行列所在开关都会被改变
-+-- 问，要打开总开关至少要改变多少次开关？并输出改变开关的位置。 思路： 由于每个开关只有两种状态，那么对于这16个小开关，我们可以用2进制来压缩下，如果开关是打开的那么为'0'，如果是关着的，那么为'1'，如此，我们就可以从下到上，从右到左给这16个开关
标记状态，如果以某个点为中心，那么这个点的行列状态都压缩进去，遇到这个点，取反与不取反，然后一次广搜过去，再记忆下路径，结果就出来了......
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define M 1<<16
int t[20]={
63624,62532,61986,61713,
36744,20292,12066,7953,
35064,17652,8946,4593,
34959,17487,8751,4383,
};
structnode
{
int k;
int step;
};
structnode1
{
int father;
int x,y;
}s[(1<<17)];
//bool vist[(1<<17)];
int sum;
void print(int ans)
{
if(ans==sum)
return;
print(s[ans].father);
printf("%d %d\n",s[ans].x+1,s[ans].y+1);
}
void bfs(int ans)
{
queue<node>q;
node p;
p.k=ans;
p.step=0;
s[p.k].father=-10;
q.push(p);
while(!q.empty())
{
p=q.front();
q.pop();
if(p.k==0)
{
printf("%d\n",p.step);
print(p.k);
return;
}
for(int i=0;i<16;i++)
{
node p1;
p1.k=p.k^t[i];
p1.step=p.step+1;
if(s[p1.k].father==-1)
{
s[p1.k].father=p.k;
s[p1.k].x=i/4;
s[p1.k].y=i%4;
q.push(p1);
}
}
}
}
int main()
{
int ans=0,cnt=15;
for(int i=0;i<4;i++)
{
char ch[100];
scanf("%s",ch);
for(int j=0;j<4;j++)
{
if(ch[j]=='+')
{
ans|=(1<<cnt);
}
cnt--;
}
}
//printf("%d\n",ans);
sum=ans;
for(int i=0;i<(M);i++)
{
s[i].father=-1;
}
bfs(ans);
return 0;
}