BFS版
结果对的，但是TLE
#include<stdio.h>int board[5][5];int rootStatus;static const int SIZE=1<<16;bool occurance[SIZE];struct Node{int s,c,i,j,pre;};class Queue{public:Queue():head(0),rear(0){for(int i=0;i<SIZE;i++)nodes[i]=NULL;};bool isEmpty(){return head>=rear;};void push(Node& node){if(nodes[rear]==NULL)nodes[rear]=new Node;nodes[rear]->c=node.c;nodes[rear]->pre=node.pre;nodes[rear]->s=node.s;nodes[rear]->i=node.i;nodes[rear]->j=node.j;rear=(rear+1)%SIZE;}void pop(Node& node){node.c=nodes[head]->c;node.pre=nodes[head]->pre;node.s=nodes[head]->s;node.i=nodes[head]->i;node.j=nodes[head]->j;head=(head+1)%SIZE;}int lastTopIndex(){return head-1;}void get(int index,Node& node){node.c=nodes[index]->c;node.pre=nodes[index]->pre;node.s=nodes[index]->s;node.i=nodes[index]->i;node.j=nodes[index]->j;}private:Node* nodes[SIZE];int head,rear;};void init(){int s=1;for(int i=4;i>=1;i–){for(int j=4;j>=1;j–){board[i][j]=s;s=s<<1;}}rootStatus=0;char a;for(int i=0;i<16;i++){scanf(" %c",&a);rootStatus=rootStatus<<1;if(a==’-‘){rootStatus^=1;}}getchar();}void print(Node& n,Queue& q){if(n.pre!=-1){Node temp;q.get(n.pre,temp);print(temp,q);printf("%d %d\n",n.i,n.j);}}int main(){init();Node n,t;Queue q;int flag=0;n.s=rootStatus;n.c=0;n.pre=-1;q.push(n);occurance[rootStatus]=1;while(!q.isEmpty()){q.pop(n);if(n.s==65535){flag=1;break;}for(int i=1;i<5;i++){for(int j=1;j<5;j++){int ts = n.s;for(int m=1;m<5;m++){ts^=board[m][j];ts^=board[i][m];}ts^=board[i][j];t.s=ts;t.pre=q.lastTopIndex();t.c=n.c+1;t.i=i;t.j=j;if(t.s==65535){flag=1;n.s=t.s;n.pre=t.pre;n.c=t.c;n.i=t.i;n.j=t.j;break;}else{if(!occurance[t.s]){q.push(t);occurance[t.s]=1;}}}if(flag==1)break;}if(flag==1)break;}if(flag==1){printf("%d\n",n.c);print(n,q);}else{printf("impossible");}return 0;DFS
235ms
#include<iostream>using namespace std;bool board[16];int is[16];int js[16];bool check(){for(int i=0;i<16;i++){if(board[i]!=1)return false;}return true;}void init(){char a;for(int i=0;i<16;i++){cin>>a;if(a==’+’){board[i]=0;}else{board[i]=1;}}}void flip(int pos){int i=pos/4;int j=pos%4;board[pos]=!board[pos];for(int m=0;m<4;m++){board[i*4+m]=!board[i*4+m];board[(m)*4+j]=!board[(m)*4+j];}}bool dfs(int pos,int step){if(check()){cout<<step<<endl;for(int i=0;i<step;i++){cout<<is[i]<<" "<<js[i]<<endl;}return true;}if(pos>=16){return false;}//1. dont change this posif(dfs(pos+1,step))return true;//2. change this posflip(pos);is[step]=pos/4+1;js[step]=pos%4+1;if(dfs(pos+1,step+1))return true;flip(pos);return false;}int main(){init();dfs(0,0);}discuss上看到的大神解题思路：
对于一个“+”，对它所在的行列的每一个位置做题目中的flip，结果是只有该“+”会变成“-”，其余位置没有变化。
于是就对初始状态下所有“+”都做一次上述操作，最终的结果是一部分位置对比初始状态做了奇数次翻转，另一部分做了偶数次。偶数次等于没翻转，，因此只要打印出奇数次的位置即可。
94MS
#include<iostream>using namespace std;bool mark[4][4];char s[4][4];int is[16];int js[16];int main(){memset(mark,0,sizeof(mark));for(int i=0;i<4;i++)cin>>s[i];for(int i=0;i<4;i++){for(int j=0;j<4;j++){if(s[i][j]==’+’){mark[i][j]=!mark[i][j];for(int k=0;k<4;k++){mark[i][k]=!mark[i][k];mark[k][j]=!mark[k][j];}}}}int count=0;for(int i=0;i<4;i++){for(int j=0;j<4;j++){if(mark[i][j]){is[count]=i+1;js[count]=j+1;count++;}}}cout<<count<<endl;for(int i=0;i<count;i++){cout<<is[i]<<" "<<js[i]<<endl;}return 0;};
才能做到人在旅途，感悟人生，享受人生。
