正文索引 [隐藏]

传送门

题目大意

《飞行员兄弟：跟随条纹象》游戏中有一个任务，玩家需要打开一个冰箱。
冰箱门上有16个把手。每个把手都可以处于两种状态之一：打开或关闭。只有当所有把手都打开时，冰箱才是打开的。手柄用矩阵4х4表示。你可以在任何位置(i,j)改变一个把手的状态(1≤i, j≤4)。然而，这也会同时改变第i行和第j列的所有手柄的状态。
你的任务是找到打开冰箱所需的最小把手切换次数。

思路

与poj1753类似，每个格子只有0或1两种状态，那么只有奇数次的操作是有效地。结合题目4×4的小规模，考虑直接枚举答案。

接下来就是思考枚举方式。因为我们知道偶数次的操作等于没有操作，那么我们可以等效处理：在对(i,j)进行切换操作时，同时对同行列的把手也进行一次操作，那么整个过程等效为仅对(i,j)进行了一次有效操作。

图源：https://www.cnblogs.com/Java-tp/p/3873557.html

参照上图，黄色区域的方格被操作了两次，等效为0次；红色区域的方格被操作了四次，等效为0次；黑色方格被操作了七次，等效为1次。

那么我们就得到了一个策略：在对某个方格(i,j)进行切换时，同时对同行列的方格也进行切换就能确保只改变(i,j)的状态。

那么我们只需要对所有”+”执行上述策略，并记录相关方格被操作的次数，最后在统计被操作数是奇数的方格就能得到所有有效操作。

代码

#include <cstdio>
#include <iostream>

using namespace std;

int ans = 0;
int cnt[5][5];
bool mp[5][5];

void switchOn(int x, int y)
{
	for(int i = 0; i < 4; i++)
	{ 
		mp[x][i] = !mp[x][i];
		if(i == x) continue;
		mp[i][y] = !mp[i][y];
	}
	cnt[x][y]++;
}

int main() 
{
	char tmp;
	for(int i = 0; i < 4; i++)
		for(int j = 0; j < 4; j++) 
		{
			cin >> tmp;
			mp[i][j] = (tmp == '-');
		}

	for(int i = 0; i < 4; i++)
		for(int j = 0; j < 4; j++)
			if(mp[i][j] == 0)
				for(int k = 0; k < 4; k++)
				{
					switchOn(i, k);
					if(k == i) continue;
					switchOn(k, j);
				}

	for(int i = 0; i < 4; i++)
		for(int j = 0; j < 4; j++)
			if(cnt[i][j] % 2)
				ans++;

	cout << ans << endl;
	for(int i = 0; i < 4; i++)
		for(int j = 0; j < 4; j++)
			if(cnt[i][j] % 2)
				cout << i + 1 << " " << j + 1 << endl;

	return 0;
}