http://poj.org/problem?id=2965
好吧终于没有图片了，这道题看起来应该简单一些吧，毕竟已经有7000多人A了，好吧，还是先看看题目再说。
题目大意：
//还是吃过晚饭后再看吧
题目：飞行员兄弟的冰箱？（感觉恶搞的成分居多，在飞机上的冰箱？？？）
这个游戏“这个飞行员兄弟：有条纹的大象（？？？？神马东西啊，难带是要把大象装冰箱？？我去，那跟飞行员有毛线关系）”，有一个问题是参与者怎么打开冰箱。
打开冰箱的门有16个把手（好吧，我也是醉了，这什么冰箱），每个把手都有两种状态，打开或者关闭，只有所有的把手都打开的时候冰箱才会被打开（制造这种冰箱的人一辈子也卖不出去一台！！！），这些把手被处理成4*4的矩阵，你可以改变在i，j（1<=i,j<=4）坐标把手的状态，当然同时第i行j列的状态也会被改变（真心服了，这货是冰箱，敢不敢严谨一些。）
任务要求是找到最少的打开冰箱的操作。
‘+’代表关闭，‘-’代表打开。
/////////已经算是无语了，现在就是在想这道题跟做的第一题有什么区别啊？？？？？好吧，区别真的不大。
先尝试写代码吧。
刚才看了输出，好吧我承认是有区别的，要把步骤带上，不过很明显可以用递归输出
错了两次，第一次时间超限，第二次是数组定义的太大（怀疑错的地方都一样）
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std; #define maxn 70000 ////////////////不要定义太大，初始化不是不浪费时间的 struct node
{
int x, y, k, pre;
}v[maxn]; int p[10][10]; int changeNum(int a[][10]);//把二维数组转化成一个数字
void change();//构造异或数组
void changeXY(int x, int y, int a[][10]);//改变xy所在坐标的行和列
void FunOut(int pre);//输出前面的所有坐标
void BFS(); int main()
{
int i, j, a[10][10], m;
char ch; memset(v, 0, sizeof(v));
BFS(); for(i=1; i<=4; i++)
for(j=1; j<=4; j++)
{
cin >> ch; if(ch == '-')
a[i][j] = 0;
else
a[i][j] = 1;
} m = changeNum(a); printf("%d\n", v[m].k-1);
FunOut(m); return 0;
}
int changeNum(int a[][10])//把二维数组转化成一个数字
{
int i, j, m=0; for(i=1; i<=4; i++)
for(j=1; j<=4; j++)
{
m = m*2 + a[i][j];
} return m;
} void FunOut(int pre)//输出前面的所有坐标
{
if(pre== 0)
return ; FunOut(v[pre].pre); printf("%d %d\n", v[pre].x, v[pre].y);
}
void BFS()
{
queue<int> Q;
v[0].k = 1;
Q.push(0); change(); while(Q.size())
{
int q = Q.front();Q.pop(); for(int i=1; i<=4; i++)
for(int j=1; j<=4; j++)
{
int m = q ^ p[i][j]; if(v[m].k == 0)
{
v[m].k = v[q].k + 1;
v[m].pre = q;
v[m].x = i;
v[m].y = j; Q.push(m);
}
}
}
}
void changeXY(int x, int y, int a[][10])//改变xy所在坐标的行和列
{
int i; for(i=1; i<=4; i++)
{
a[x][i] = 1 - a[x][i];
a[i][y] = 1 - a[i][y];
}
a[x][y] = 1 - a[x][y];
} void change()//构造异或数组
{
int i, j, b[10][10] = {0}; for(i=1; i<=4; i++)
for(j=1; j<=4; j++)
{
changeXY(i, j, b);
p[i][j] = changeNum(b);
changeXY(i, j, b);
}
}