当前位置: 代码迷 >> 综合 >> 枚举 poj2965 The Pilots Brothers' refrigerator
  详细解决方案

枚举 poj2965 The Pilots Brothers' refrigerator

热度:59   发布时间:2023-12-14 04:10:01.0

这题的思路非常值得深思


先考虑这种情况

-+--

-+--

++++

-+--


用一个数组vis作标记数组

然后遍历所有的+的位置,将+所在的行和列的vis都翻转(0变1,1变0),那么会怎样呢?

首先肯定可以证明,翻转偶数次和没翻转是一样的,翻转只分奇数次和偶数次就够了


先看左上角,左下角,右上角,右下角,这4块会同时受到行和列+号的影响,所以抵消了不变

再看除了十字中间那个+的其他+的位置,其他的+的操作次数都是4次,所以也不变,还是0

中间那个+的位置,被翻转了7次,是奇数次,所以会变成1!

所以会得到的vis数组是

0 0 0 0

0 0 0 0

0 1 0 0

0 0 0 0

此时这个1恰好就是答案!

所以我们只要按照+所在的位置去翻转,最后得到的vis数组中,1的位置就是答案的位置!


#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 50 + 5;
const int INF = 0x3f3f3f3f;bool vis[MX][MX];
char S[MX][MX];int ax[MX], ay[MX], tot;int main() {while(~scanf("%s", S[1] + 1)) {tot = 0;memset(vis, 0, sizeof(vis));for(int i = 2; i <= 4; i++) {scanf("%s", S[i] + 1);}for(int i = 1; i <= 4; i++) {for(int j = 1; j <= 4; j++) {if(S[i][j] == '+') {vis[i][j] ^= 1;for(int k = 1; k <= 4; k++) {vis[i][k] ^= 1;vis[k][j] ^= 1;}}}}for(int i = 1; i <= 4; i++) {for(int j = 1; j <= 4; j++) {if(vis[i][j]) {tot++;ax[tot] = i;ay[tot] = j;}}}printf("%d\n", tot);for(int i = 1; i <= tot; i++) {printf("%d %d\n", ax[i], ay[i]);}}return 0;
}