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