poj2965(位运算压缩+bfs+记忆路径)

题意：有个4*4的开关，里面有着16个小开关

-+--

----

----     '+'表示开关是关着的，'-'表示开关是开着的，只有所有的开关全被打开，总开关才会被打开。现在有一种操作，只要改变某个开关，那么这个开关的行列所在开关都会被改变

-+--      问，要打开总开关至少要改变多少次开关？并输出改变开关的位置。

思路： 由于每个开关只有两种状态，那么对于这16个小开关，我们可以用2进制来压缩下，如果开关是打开的那么为'0'，如果是关着的，那么为'1'，如此，我们就可以从下到上，从右到左给这16个开关
标记状态，如果以某个点为中心，那么这个点的行列状态都压缩进去，遇到这个点，取反与不取反，然后一次广搜过去，再记忆下路径，结果就出来了......

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

#define M 1<<16

int t[20]={

    63624,62532,61986,61713,

    36744,20292,12066,7953,

    35064,17652,8946,4593,

    34959,17487,8751,4383,

};

structnode

{

    int k;

    int step;

};

structnode1

{

    int father;

    int x,y;

}s[(1<<17)];

//bool vist[(1<<17)];

int sum;

void print(int ans)

{

    if(ans==sum)

    return;

    print(s[ans].father);

    printf("%d %d\n",s[ans].x+1,s[ans].y+1);

}

void bfs(int ans)

{

    queue<node>q;

    node p;

    p.k=ans;

    p.step=0;

    s[p.k].father=-10;

    q.push(p);

    while(!q.empty())

    {

        p=q.front();

        q.pop();

        if(p.k==0)

        {

            printf("%d\n",p.step);

            print(p.k);

            return;

        }

        for(int i=0;i<16;i++)

        {

            node p1;

            p1.k=p.k^t[i];

            p1.step=p.step+1;

            if(s[p1.k].father==-1)

            {

                s[p1.k].father=p.k;

                s[p1.k].x=i/4;

                s[p1.k].y=i%4;

                q.push(p1);

            }

        }

    }

}

int main()

{

    int ans=0,cnt=15;

    for(int i=0;i<4;i++)

    {

        char ch[100];

        scanf("%s",ch);

        for(int j=0;j<4;j++)

        {

            if(ch[j]=='+')

            {

                ans|=(1<<cnt);

            }

            cnt--;

        }

    }

    //printf("%d\n",ans);

    sum=ans;

    for(int i=0;i<(M);i++)

    {

        s[i].father=-1;

    }

    bfs(ans);

    return 0;

}

巴特西

poj2965(位运算压缩+bfs+记忆路径)

最新文章

热门文章