《算法竞赛进阶指南》0x08 T1 The Pilot‘s Brother‘s Refrigerator

题目描述

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 $16$ 个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个 $4\times 4$ 的矩阵，您可以改变任何一个位置 $[i,j]$ 上把手的状态。
但是，这也会使得第 $i$ 行和第 $j$ 列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式

输入一共包含四行，每行包含四个把手的初始状态。
符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。

输出格式

第一行输出一个整数 $N$，表示所需的最小切换把手次数。
接下来 $N$ 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

数据范围

$1\le i,j\le 4$

输入样例：

$-+--$
$----$
$----$
$-+--$

输出样例：

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

题解

用状态压缩解决此题，暴力枚举出点亮每个灯的情况，用二进制数表示状态
然后按照题目要求，把位置是1的灯所在的行与列调转成相反的状态（fz函数）
统计修改后是否所有灯都打开
在所有符合情况的状态中找调整次数的最小值，并存储要改变的灯的编号即可

code

#include<bits/stdc++.h>
using namespace std;
char a[100][100],b[100][100];
int ansx[100],ansy[100];
int X(int x)//把二进制数的位数转化为横坐标
{
	if(x>=0&&x<=3) return 1;
	if(x>=4&&x<=7) return 2;
	if(x>=8&&x<=11) return 3;
	if(x>=12&&x<=15) return 4; 
	return 0;
}
int Y(int x)//把二进制数的位数转化为纵坐标
{
	if(x==0||x==4||x==8||x==12) return 1;
	if(x==1||x==5||x==9||x==13) return 2;
	if(x==2||x==6||x==10||x==14) return 3;
	if(x==3||x==7||x==11||x==15) return 4;
	return 0;
}
char fz(char x)//将灯的状态改变
{
	if(x=='+') return '-';
	else return '+';
}
int main()
{
	int maxn=-1;
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			cin>>a[i][j];
	for(int i=1;i<=(1<<16)-1;i++)
	{
		int sum=0;
		
		for(int j=1;j<=4;j++)
			for(int k=1;k<=4;k++)
				b[j][k]=a[j][k];
		for(int j=0;j<16;j++)
		{
			if((i>>j)&1)
			{
				sum++;
				for(int k=1;k<=4;k++) b[X(j)][k]=fz(b[X(j)][k]);
				for(int k=1;k<=4;k++) b[k][Y(j)]=fz(b[k][Y(j)]);
				b[X(j)][Y(j)]=fz(b[X(j)][Y(j)]);
			}
		}
		bool f=0;
		for(int j=1;j<=4;j++)
		{
			for(int k=1;k<=4;k++)
			{
				if(b[j][k]=='+')
				{
					f=1;
					break;
				}
			}
			if(f==1) break; 
		}
		if(f==1) continue;
		else
			if(sum>maxn)
			{
				maxn=sum;
				int tot=0;
				for(int j=0;j<16;j++)
					if((i>>j)&1)
					{
						ansx[++tot]=X(j);
						ansy[tot]=Y(j);
					}
			}
	}
	cout<<maxn<<endl;
	for(int i=1;i<=maxn;i++) cout<<ansx[i]<<' '<<ansy[i]<<endl;
	return 0;
}