Fork me on GitHub

POJ 1753 Flip Game(状压+搜索)

发表于 | 分类于

原题

题目大意：

题目中给出4*4的状态图包括’b’,’w’,要求全部翻转成’b’或’w’， 每次翻转一个位置,那么它的上下左右四个位置也要翻转(如果有的话)。要求算出最小翻转次数。

题解：

因为题目数据量不大，所以其实一维二维都可以。在这里将矩阵用一串二进制数表示，异或操作进行翻转，注意判断行列。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# include<iostream>
# include<cstdio>
# include<algorithm>
# include<cstring>
# include<cmath>
using namespace std;
# define ll long long
int num[17]= {0};
int k;
int pd()//判断是否全部同向
{
    int i;
    for(i=2; i<=16; i++)
        if(num[i]!=num[i-1])return 0;
    return 1;
}
void fz(int i)//翻转操作
{
    num[i]^=1;
    if(i%4!=0)num[i+1]^=1;//不在最后一列
    if(i%4!=1)num[i-1]^=1;//不在第一列
    if(i>4)num[i-4]^=1;//不在第一行
    if(i<13)num[i+4]^=1;//不在最后一行
}
void bfs(int j,int now,int all)//枚举过程，j指到了第几个棋子，now指现在翻转的次数，all指这一轮应当翻转的总次数（1-16）
{
    int i;
    if(now==all)//翻转次数到这一轮最大值
    {
        k=pd();
        return;
    }
    for(i=j+1; i<=16; i++)//广搜本质
    {
        fz(i);
        bfs(i,now+1,all);
        if(k) return;
        fz(i);//还原。
    }
}
int main()
{
    char a;
    int i;
    ios::sync_with_stdio(false);
    for(i=1; i<=16; i++)
    {
        cin>>a;
        if(a=='w')
            num[i]=1;
    }
    k=pd();
    if(k)cout<<0<<endl;
    else
    {
        for( i=1; i<=16; i++)//一次遍历找出最小翻转次数
        {
            k=0;
            bfs(0,0,i);
            if(k)break;
        }
        if(k)cout<<i<<endl;
        else cout<<"Impossible"<<endl;
    }
return 0;
}