ACwing 116. 飞行员兄弟 dfs 二进制枚举

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有16个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个4х4的矩阵，您可以改变任何一个位置[i,j]上把手的状态。

但是，这也会使得第i行和第j列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式

输入一共包含四行，每行包含四个把手的初始状态。

符号“+”表示把手处于闭合状态，而符号“-”表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。
输出格式

第一行输出一个整数N，表示所需的最小切换把手次数。

接下来N行描述切换顺序，每行输入两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
数据范围

1≤i,j≤4

输入样例：

-±-

-±-

输出样例：

6
1 1
1 3
1 4
4 1
4 3
4 4

注意点 :

• 同一个开关按两次是没有意义的, 所以最多按16次
• $我们用二进制位代表开或关的状态比如000101表示第3和第1个开关是关闭的$我们用二进制位代表开或关的状态比如000101表示第3和第1个开关是关闭的
• 我们直接把二进制亦或一个数字 $X$X, 就可以得到操作同行同列的结果
  对于每个编号的 $X$X要提前预处理出来,用 $change\left[\right]$change[ ]数组记录这个数字 $X$X
• 我们把4*4的网格编号[0, 15]

$0123$ 0      1      2      3
$4567$ 4      5      6      7
$891011$ 8      9     10     11
$12131415$12     13     14     15

• 并用pi[]数组记录每个编号对应行列下标
  爆搜每个编号的位置按或不按的结果
  用status记录当前状态 操作完后status等于0就说明全开
• 题目要求字典序最小 : 按行递增,行内按列递增即可
• 取得第i行第k列的编号的公式 : $(i\ast 4+k)$(i∗4+k)
• 判断数字第i位是否为1方法 : if(numi&1)
• y总牛逼!!!视频链接:https://www.acwing.com/video/93/

#define debug
#ifdef debug
#include <time.h>
#include </home/majiao/mb.h>
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN (8)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO{

	char print_f[105];
	void read() {}
	void print() { putchar('\n'); }

	template <typename T, typename... T2>
	   inline void read(T &x, T2 &... oth) {
		   x = 0;
		   char ch = getchar();
		   ll f = 1;
		   while (!isdigit(ch)) {
			   if (ch == '-') f *= -1; 
			   ch = getchar();
		   }
		   while (isdigit(ch)) {
			   x = x * 10 + ch - 48;
			   ch = getchar();
		   }
		   x *= f;
		   read(oth...);
	   }
	template <typename T, typename... T2>
	   inline void print(T x, T2... oth) {
		   ll p3=-1;
		   if(x<0) putchar('-'), x=-x;
		   do{
				print_f[++p3] = x%10 + 48;
		   } while(x/=10);
		   while(p3>=0) putchar(print_f[p3--]);
		   putchar(' ');
		   print(oth...);
	   }
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K;
int change[MAXN<<2];

/** 同一个开关按两次是没有意义的, 所以最多按16次 我们用二进制位代表开或关的状态 比如 0 0 0 1 0 1 表示第3和第1个开关是关闭的 我们直接把二进制亦或一个数字 X, 就可以得到操作同行同列的结果 对于每个编号的X要提前预处理出来,用change[]数组记录这个数字X 我们把4*4的网格编号[0, 15] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 并用pi[]数组记录每个编号对应行列下标 爆搜每个编号的位置按或不按的结果 用status记录当前状态 操作完后status等于0就说明全开 题目要求字典序最小 : 按行递增,行内按列递增即可 取得第i行第k列的编号的公式 : ( i * 4 + k ) 判断数字第i位是否为1方法 : if( num >> i & 1 ) */

#define get(i, k) (i*4+k) //返回第i行第k列的编号
typedef pair<int, int> pii;
pii pi[MAXN<<4]; //记录每个编号对应的行列下标

signed main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	int status = 0; //把status的所有二进制位都变成0就是一个解决方案
	for(int i=0; i<4; i++) {
		char buf[MAXN];
		scanf("%s ", buf);
		for(int j=0; j<4; j++) { //标记所有闭则的为1
			if(buf[j] == '+') 
				status |= (1 << get(i, j));
			pi[get(i, j)] = { i+1, j+1 }; //记录每个编号的行列
		}
	}

	for(int i=0; i<4; i++) //预处理所有位置应该亦或什么值X
		for(int j=0; j<4; j++) {
			for(int k=0; k<4; k++) change[get(i, j)] += (1<<get(i, k));
			for(int k=0; k<4; k++) change[get(i, j)] += (1<<get(k, j));
			change[get(i, j)] -= (1 << get(i, j));
		}

	int N = 1 << 16; //最多2^16种方案
	vector<pii> ans(32, pii()); //存储答案
	for(int i=1; i<N; i++) {
		int now = status, cnt = 0; //用now来表示当前状态
		vector<pii> vec;
		for(int j=0; j<16; j++) {
			if(i >> j & 1) //操作编号为j的位置
				now ^= change[j], vec.push_back(pi[j]), cnt ++;
		}
		if(!now && ans.size() > vec.size()) {
			ans = vec;
			//printf("%d\n", cnt);
			//for(auto v : vec)
			// printf("%d %d\n", v.first, v.second);
		}
	}
	if(!ans.size()) { printf("-1\n"); return 0; }
	printf("%d\n", (int)ans.size());
	for(auto v : ans)
		printf("%d %d\n", v.first, v.second);




#ifdef debug
   clock_t etime = clock();
   printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
   return 0;
}