Fork me on GitHub

POJ 2965- The Pilots Brothers' refrigerator

发表于 | 分类于

##POJ 2965-The Pilots Brothers’ refrigerator

原题

题目大意：

题目中给出的状态图包括’+’,’-‘,要求将其全部翻转成’-‘，每次翻转一个位置,那么它所在的行和列都要翻转

问最小翻转次数,同时输出翻转路径。

题解：

这道题和POJ 1753相似，但这里借鉴到了更好的算法：

情况：

1、这道题不存在impossible的情况，说明最多把所有‘+’都改一次可以实现全部符号为‘-’。

2、这道题的关键在于如何改变‘+’，而不改变与它关联的行和列。

解决：

实现1：用一个二维数组初始化为0，’+‘的位置记为1，接下来依次改变’+‘的位置并用它记录矩阵各位置的改动次数，最后对2取模。/ 当某位置最后的改动次数为偶数，对2取模为0，说明该位置同初始情况相比没有改变，不需要改动 / 最后只需搜索数组中奇数的个数就是答案。

实现2：思路同上，具体操作改为用bool型数组记录改动次数，最后找到值为true的数量就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
bool vis[4][4];
char num[4][4];
int main()
{
    int i,j,k;
    int ii[17],jj[17];
    int ans=0;
    memset(vis,0,sizeof(vis));
    for(i=0; i<4; i++)
        cin>>num[i];
           for(i=0; i<4; i++)//找到'+'的情况进行改动
        {
            for(j=0; j<4; j++)
            {
                if(num[i][j]=='+')
                {
                    vis[i][j]=!vis[i][j];
                    for(int k=0; k<4; k++)//对关联行列改动
                    {
                        vis[i][k]=!vis[i][k];
                        vis[k][j]=!vis[k][j];
                    }
                }
            }
        }
    for(i=0; i<4; i++)//判断是否需要改动
        for(j=0; j<4; j++)
            if(vis[i][j]==1)
            {
                ii[ans]=i+1;
                jj[ans]=j+1;
                ans++;
            }
    cout<<ans<<endl;
    for(i=0; i<ans; i++)
        cout<<ii[i]<<' '<<jj[i]<<endl;
    return 0;
}