本文共 2747 字，大约阅读时间需要 9 分钟。

The Pilots Brothers' refrigerator

Description

The game “The Pilots Brothers: following the stripy elephant” has a quest where a player needs to open a refrigerator.

There are 16 handles on the refrigerator door. Every handle can be in one of two states: open or closed. The refrigerator is open only when all handles are open. The handles are represented as a matrix 4х4. You can change the state of a handle in any location [i, j] (1 ≤ i, j ≤ 4). However, this also changes states of all handles in row i and all handles in column j.

The task is to determine the minimum number of handle switching necessary to open the refrigerator.

Input

The input contains four lines. Each of the four lines contains four characters describing the initial state of appropriate handles. A symbol “+” means that the handle is in closed state, whereas the symbol “−” means “open”. At least one of the handles is initially closed.

Output

The first line of the input contains N – the minimum number of switching. The rest N lines describe switching sequence. Each of the lines contains a row number and a column number of the matrix separated by one or more spaces. If there are several solutions, you may give any one of them.

Sample Input

-+-----------+--

Sample Output

61 11 31 44 14 34 4

Source

, Western Subregion

大致题意：

一个4*4的开关棋盘，+代表close,-代表open，当改变一个开关状态时，与其同一行和同一列的开关也改变状态

要求解出所有开关状态都为open的最少步骤，以及每一步操作的坐标。

解题思路：

首先，要明确一个基本概念，当一个位置改变偶数次相当于改变0次，当改变奇数次，相当于改变1次

然后，对于这道题

第一步，就是需要找出棋盘中+状态的位置，我们发现当改变这个位置的开关时，同行和同列的开关也会改变

因此，要求把同行和同列位置的要变回来

找到的策略就是：

把开关本身以及其同一行同一列的开关（总共7个）都进行一次操作，

结果是，开关本身状态改变了7次，

开关同一行、同一列的开关状态改变了4次，

其他开关状态改变了2次。

如下图所示。

假如开关坐标为第二行第三列的（2，3），那么按照上述策略（把开关本身以及其同一行同一列的开关都进行一次操作），

结果分析如下：

对于黄色部分的开关：

只有与此黄色开关同一行和同一列的两个红色开关操作时，此黄色开关的状态才会发生改变，

因此所有黄色部分状态改变次数为2，相当于0次

对于红色部分的开关，

只有与此红色开关同一列或同一列的开关操作时，此红色开关状态才会发生改变，一行或者一列有4个开关，

因此红色部分开关状态改变次数为4，相当于0次

对于最原始的那个黑色开关，

所有红色开关操作时，它的状态改变一次，然后黑色开关自己操作一次，因此黑色开关状态改变7次，相当于改变1次。

总结上述分析可以得出结论，

把开关本身以及其同一行同一列的开关都进行一次操作，最终结果是只有开关本身状态发生变化，其他所有开关状态都不变。

策略找到之后，那我们就想，如果对于所有关闭着的开关都进行一次上述策略，那么肯定是能把冰箱打开的，下面我们要做的

就是把一些无用的，重复的操作去掉即可。

用一个4*4的数组记录每个开关操作的次数，初始化为0，开关操作一次，记录就+1。

那么，重复需要去除的操作就是操作记录为偶数的。

代码：

#include 
   
    using namespace std;void change(int aa[4][4],int i,int j){	for(int k=0;k<4;k++)	{ 		aa[i][k]++;		aa[k][j]++;	}	aa[i][j]--; //去掉重复的那一次}int main() {    char a[4][4];//棋盘	int aa[4][4]={0};//记录	int sum=0;//总次数	int res[16][2];//结果	for(int i=0;i<4;i++)	for(int j=0;j<4;j++)	cin>>a[i][j];	for(int i=0;i<4;i++)	for(int j=0;j<4;j++)	{		if(a[i][j]=='+')		change(aa,i,j);	}		for(int i=0;i<4;i++)	for(int j=0;j<4;j++)	{		if(aa[i][j]%2!=0)		{ 		    res[sum][0]=i;		    res[sum][1]=j;			sum++;					}	}	cout<
    
     <
    
   

转载地址：https://joycez.blog.csdn.net/article/details/82142528 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！