POJ-2965 The Pilots Brothers' refrigerator---思维题

时间:2024-09-02 20:33:32

题目链接:

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

题目大意:

一个冰箱上有4*4共16个开关,改变任意一个开关的状态(即开变成关,关变成开)时,此开关的同一行、同一列所有的开关都会自动改变状态。要想打开冰箱,要所有开关全部打开才行。

思路:

一开始以为是和POJ1753一样的套路,直接枚举,结果TLE(无语)。后来百度之后发现都是这样,不能直接枚举

首先要明白最基本的原理:对一个开关进行操作n次,如果n为偶数,那么这个开关以及同行、同列的开关状态都不发生改变,等价于没有操作;如果n为奇数,那么这个开关以及同行同列的开关状态全都发生改变,等价于只操作了一次。

要想使所有开关状态全部打开(全部是-),就要把所有+变成-,所有-不改变。我们要做的就是找到一种“公式”,策略,使得不改变已经打开的开关状态的情况下,把关闭的开关打开。这点很类似于魔方(PS:玩过魔方的都知道,魔方所谓的公式,其实就是在不改变已经拼好的部分的情况下,把其他部分一点一点添加到已拼好的部分)。

我们找到的策略就是:把开关本身以及其同一行同一列的开关(总共7个)都进行一次操作,结果是,开关本身状态改变了7次,开关同一行、同一列的开关状态改变了4次,其他开关状态改变了2次。如下图所示。

POJ-2965 The Pilots Brothers' refrigerator---思维题

假如开关坐标为第二行第三列的(2,3),那么按照上述策略(把开关本身以及其同一行同一列的开关都进行一次操作),结果分析如下:

对于黄色部分的开关,只有与此黄色开关同一行和同一列的两个红色开关操作时,此黄色开关的状态才会发生改变,因此所有黄色部分状态改变次数为2,相当于0次

对于红色部分的开关,只有与此红色开关同一列或同一列的开关操作时,此红色开关状态才会发生改变,一行或者一列有4个开关,因此红色部分开关状态改变次数为4,相当于0次

对于最原始的那个黑色开关,所有红色开关操作时,它的状态改变一次,然后黑色开关自己操作一次,因此黑色开关状态改变7次,相当于改变1次。

总结上述分析可以得出结论,把开关本身以及其同一行同一列的开关都进行一次操作,最终结果是只有开关本身状态发生变化,其他所有开关状态都不变。

策略找到之后,那我们就想,如果对于所有关闭着的开关都进行一次上述策略,那么肯定是能把冰箱打开的,下面我们要做的就是把一些无用的,重复的操作去掉即可。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + ;
const int INF = << ;
int T, n, m;
bool a[][], b[][], v[][];
int dir[][] = {,,,,-,,,-};
int main()
{
for(int i = ; i < ; i++)
{
for(int j = ; j < ; j++)
{
char c = getchar();
if(c == '+')
{
a[i][j] = !a[i][j];
for(int k = ; k < ; k++)
{
a[i][k] = !a[i][k];
a[k][j] = !a[k][j];
}
}
}
getchar();
}
int tot = ;
for(int i = ; i < ; i++)
{
for(int j = ; j < ; j++)
{
if(a[i][j])tot++;
}
}
cout<<tot<<endl;
for(int i = ; i < ; i++)
{
for(int j = ; j < ; j++)
{
if(a[i][j])cout<<(i + )<<" "<<(j + )<<endl;
}
}
return ;
}