「POJ2965」The Pilots Brothers' refrigerator

题目链接 & 题面

AcWing：https://www.acwing.com/problem/content/118/

VirtualJudge：https://vjudge.net/problem/POJ-2965

题目描述

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

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

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

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

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

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

输入格式

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

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

至少一个手柄的初始状态是关闭的。

输出格式

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

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

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

数据范围

1≤i,j≤4

基本思路

DFS

要想解法最优，首先要保证一个一个把手最多切换1次，如果切换1次以上就是浪费次数。

例如切换2次，和不切换效果相同，切换3次，和切换1次效果相同……不管这n次切换中间经历了什么，最后的效果是和0或1次切换效果相同。

这个非常容易证明，只需要证明操作是无序的即可。其实题目输出的排序，也暗示了这点。

并且，如果不重复切换的话，每种情况是有唯一解的。

这点是我的直觉告诉我的（真的很显而易见），也就是说，题目中“多种打开冰箱的方式”也只是打开的顺序不同，解法是相同的。

这样，对于一个把手，只有切换和不切换两种状态，状态空间大小为 $2^{16}$ ，也就是65536，完全可以考虑深搜。

二进制状态压缩

其实对于这道题，一共就4×4的范围，没什么必要弄状态压缩，但看在书上和 AcWing 给了位运算的tag，就写一下吧，实际优化的程度并不大。

把当前状态用16位二进制表示，我选择的是从左到右，从上到下（和数据输出的顺序相同）。

每次改变把手的时候就让相应的位和1做异或运算。

由于我用1表示闭合，用0表示打开，所以当这个二进制数等于0的时候，说明找到了解（并且是唯一解），输出。

代码

#include <cstdio>
#include <iostream>

void dfs(int);
int mkbin(int);
int pow(int, int);
char a;
int r, b, x, y, logx[20], logy[20], cnt, ans;

int main(){
	freopen("data.in", "r", stdin);

	for(int i=0; i<16; i++){
		scanf("%c", &a);
		if(a=='\n') i--;
		if(a=='+') { r*=2; r+=1; }
		if(a=='-') r*=2;
	}
	dfs(0);

	return 0;
}

void dfs(int step){
	if(r==0){
		printf("%d\n", cnt);
		for(int i=0; i<cnt; i++){
			printf("%d %d\n", logx[i], logy[i]);
		}
		return;
	}
	if(step==16) return;
	
	dfs(step+1);
	int b = mkbin(step);
	r = r^b;
	logx[cnt]=step/4+1;
	logy[cnt]=step%4+1;
	cnt++;
	dfs(step+1);
	r = r^b;
	cnt--;
}

int mkbin(int num){
	ans=0;
	x=num/4; y=num%4;
	ans^=15*pow(16, 3-x);
	ans^=pow(2, 3-y)*1;
	ans^=pow(2, 3-y)*16;
	ans^=pow(2, 3-y)*256;
	ans^=pow(2, 3-y)*4096;
	ans^=pow(2, 3-y)*pow(16, 3-x);
	return ans;
}

int pow(int c, int d){
	int anss=1;
	for(int i=0; i<d; i++) anss*=c;
	return anss;
}