题意:给定一个4*4矩阵状态，代表门的16个把手。‘+’代表关，‘-’代表开。当16个把手都为开（即‘-’）时。门才干打开，问至少要几步门才干打开
改变状态规则：选定16个把手中的随意一个，能够改变其本身以及同行同列的状态（即若为开，则变为关，若为关，则变为开），这一次操作为一步.
分析：这题与poj 1753思路差点儿相同，每一个把手最多改变一次状态，
全部整个矩阵最多改变16次状态
思路：直接dfs枚举全部状态，直到找到目标状态
可是要打印路径，全部应在dfs时记录路径
注意：能够用位运算操作。这样比較快。若直接推断‘+’‘-’状态变换，非常可能超时
<pre name="code" class="cpp">#include<stdio.h>
int s[5][5],step,r[20],c[20],flag;
int judge() //推断把手是否全开
{
int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(s[i][j])
return 0;
return 1;
}
void flip(int i,int j) //改变状态
{
int k;
s[i][j]=!s[i][j];
for(k=0;k<4;k++){
s[i][k]=!s[i][k];
s[k][j]=!s[k][j];
}
}
void dfs(int i,int j,int num)
{
if(num==step){
flag=judge();
return ;
}
if(flag||i==4)
return ;
flip(i,j);
r[num]=i; //记录路径
c[num]=j;
if(j<3)
dfs(i,j+1,num+1);
else
dfs(i+1,0,num+1);
flip(i,j); //回溯
if(j<3)
dfs(i,j+1,num);
else
dfs(i+1,0,num);
return ;
}
int main()
{
int i,j;
char t;
for(i=0;i<4;i++){
for(j=0;j<4;j++){
scanf("%c",&t);
if(t=='+')
s[i][j]=1; //用0标记开，1标记关，方便位运算
else
s[i][j]=0;
}
getchar();
}
for(step=0;step<=16;step++){
dfs(0,0,0);
if(flag)
break;
}
printf("%d\n",step);
for(i=0;i<step;i++)
printf("%d %d\n",r[i]+1,c[i]+1);
return 0;
}