poj1753（位运算压缩状态+bfs）

水深无声 2022-03-31 03:47 227阅读 0赞

题意：有个4\*4的棋盘，上面摆着黑棋和白旗，b代表黑棋，w代表白棋，现在有一种操作，如果你想要改变某一个棋子的颜色，那么它周围（前后左右）棋子的颜色都会被改变（白变成黑，黑变成白），问你将所有棋子变成白色或者黑色最少的步数。

思路：状态压缩+搜索。对于

![08142722-a0daa8cfabf94867b886835d80f4a7f3.x-png][]

![08142830-371329db5ada476ea6d2311fc44e7d12.jpg][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    int t[20]={
        51200,58368,29184,12544,
        35968,20032,10016,4880,
        2248,1252,626,305,
        140,78,39,19,
    };
    int M=1<<16;
    bool vist[(1<<16)];
    struct node
    {
        int k;
        int step;
    };
    
    void bfs(int ans)
    {
        queue<node>q;
        node p;
        p.k=ans;
        p.step=0;
        q.push(p);
        while(!q.empty())
        {
            p=q.front();
            q.pop();
            if(p.k==0||p.k==(M-1))
            {
                printf("%d\n",p.step);
                return;
            }
            for(int i=0;i<16;i++)
            {
                node p1;
                p1.step=p.step+1;
                p1.k=p.k^t[i];
                if(!vist[p1.k])
                {
                    vist[p1.k]=true;
                    q.push(p1);
                }
            }
        }
        printf("Impossible\n");
    }
    int main()
    {
        int ans=0,cnt=15;
        for(int i=0;i<4;i++)
        {
            char ch[10];
            scanf("%s",ch);
            for(int j=0;j<4;j++)
            {
                if(ch[j]=='w')
                {
                    ans|=(1<<cnt);
                }
                cnt--;
            }
        }
        memset(vist,false,sizeof(vist));
        vist[ans]=true;
        bfs(ans);
        return 0;
    }

[08142722-a0daa8cfabf94867b886835d80f4a7f3.x-png]: /images/20220331/b28e8d5ce2ef47fcaa0076f1ce79cc5a.png
[08142830-371329db5ada476ea6d2311fc44e7d12.jpg]: /images/20220331/1be246e919de4d61aef1086b4d267b9a.png