继poj1753继续训练枚举算法：
这道题相比1753有两个改变：
一、从小十字变成了大十字（从改变一个点的上下左右变成了一个点的整行整列），这个倒是不难做，执行函数稍微改一下就行
二、题目直接让你输出改变的点(这道题是special judge)，不过我直接把1753的寻找最小步数的思路拿来了，其实只要找到全部为open的一个解就行了
思路差不多，不多解释了，直接上代码（吐槽一下edge，贴代码总是崩溃，google不会崩）
#include<stack>
#include<iostream>
using namespace std;char temp[4][4];
bool jud[4][4];
int temp_min;
int Min = 0x7fffffff;
typedef struct {
int x;int y;
}POINT;
stack<POINT>Q,t;void change(int n1, int n2) {
//改变一个点temp[n1][n2] == '+' ? temp[n1][n2] = '-' : temp[n1][n2] = '+';
}
void change_point(int n1, int n2) {
//把这个点对应所有改变的点都改变for (int i = 0; i < 4; i++) {
change(n1,i);//把一行的都改了change(i,n2);//把一列的改了}change(n1, n2);//重复的点
}
bool isOk() {
//判断是否达成目标，这道题的话可以直接输出结果了，不改了for (int i = 0; i < 4; i++)for (int j = 0; j < 4; j++) {
if (temp[i][j] != '-')//'-'才是打开啊啊啊啊啊啊啊return false;}return true;
}
void dfs(int n1,int n2) {
if (isOk()) {
Min = Min < temp_min ? Min : temp_min;Q=t;return;}if (n2 == 4) {
dfs(n1 + 1, 0);return;}if (n1 == 4) {
return;}//动if (!jud[n1][n2]) {
//没有翻过jud[n1][n2] = true;//标记已经翻过POINT te = {
n1,n2 };//吐槽一下，直接push{n1,n2}交不上去t.push(te);//进入队列change_point(n1, n2);temp_min++;dfs(n1, n2 + 1);t.pop();jud[n1][n2]=false;change_point(n1, n2);//状态改回原样temp_min--;}//不动dfs(n1, n2 + 1);
}
void Out(stack<POINT>&q) {
POINT t;if (q.size()) {
t = q.top();q.pop();Out(q);printf("%d %d\n", t.x + 1, t.y + 1);}
}
int main() {
int i, j;for (i = 0; i < 4; i++) {
for (j = 0; j <4; j++) {
scanf("%c", &temp[i][j]);}getchar();}dfs(0,0);if (Min == 0x7fffffff) cout << "Impossible" << endl;//poj1753带来的，懒得改了，//顺道一提，这道题证明了本题中无论4*4矩阵是2^16个情况任意情况都有使其全部为-的解对应else {
cout << Min << endl;Out(Q);}rerurn 0;
}
另外说一下，这里我直接用栈存储解，用了后进先出的特点，实际上在dfs用数组存储也是可行的，见别人的题解，直接把16当做dfs参数便于在dfs函数中存储数据