bzoj1054: [HAOI2008]移动玩具状压+爆搜即可

题意:在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初的玩具状态移动到某人心中的目标状态。

题解:状压状态,然后bfs时枚举每一位向四个方向转移即可,记得加vis,表示已经访问过的状态

/**************************************************************

    Problem: 1054

    User: walfy

    Language: C++

    Result: Accepted

    Time:28 ms

    Memory:6176 kb

****************************************************************/

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double eps=1e-6;

const int N=1000000+10,maxn=1000000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

bool vis[N];

int dis[N];

bool left(int u,int i)

{

    if(i!=0&&i!=4&&i!=8&&i!=12&&(!((u>>(i-1))&1)))return 1;

    return 0;

}

bool right(int u,int i)

{

    if(i!=3&&i!=7&&i!=11&&i!=15&&(!((u>>(i+1))&1)))return 1;

    return 0;

}

bool up(int u,int i)

{

    if(i!=0&&i!=1&&i!=2&&i!=3&&(!((u>>(i-4))&1)))return 1;

    return 0;

}

bool down(int u,int i)

{

    if(i!=12&&i!=13&&i!=14&&i!=15&&(!((u>>(i+4))&1)))return 1;

    return 0;

}

void bfs(int x,int y)

{

    vis[x]=1;

    queue<int>q;

    q.push(x);

    while(!q.empty())

    {

        int u=q.front();

        if(u==y)

        {

            printf("%d\n",dis[u]);

            return ;

        }

        q.pop();

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

        {

            if((u>>i)&1)

            {

                if(left(u,i))

                {

                    int te=u^(1<<i)^(1<<(i-1));

                    if(!vis[te])

                    {

                        q.push(te);

                        dis[te]=dis[u]+1;

                        vis[te]=1;

                    }

                }

                if(right(u,i))

                {

                    int te=u^(1<<i)^(1<<(i+1));

                    if(!vis[te])

                    {

                        q.push(te);

                        dis[te]=dis[u]+1;

                        vis[te]=1;

                    }

                }

                if(up(u,i))

                {

                    int te=u^(1<<i)^(1<<(i-4));

                    if(!vis[te])

                    {

                        q.push(te);

                        dis[te]=dis[u]+1;

                        vis[te]=1;

                    }

                }

                if(down(u,i))

                {

                    int te=u^(1<<i)^(1<<(i+4));

                    if(!vis[te])

                    {

                        q.push(te);

                        dis[te]=dis[u]+1;

                        vis[te]=1;

                    }

                }

            }

        }

    }

}

char s[5];

int main()

{

    int x=0,y=0;

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

    {

        scanf("%s",s);

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

            if(s[j]=='1')

                x+=(1<<(i*4+j));

    }

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

    {

        scanf("%s",s);

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

            if(s[j]=='1')

                y+=(1<<(i*4+j));

    }

    bfs(x,y);

    return 0;

}

/********************

********************/

巴特西

bzoj1054: [HAOI2008]移动玩具状压+爆搜即可

最新文章

热门文章

巴特西

bzoj1054: [HAOI2008]移动玩具 状压+爆搜即可

最新文章

热门文章

bzoj1054: [HAOI2008]移动玩具状压+爆搜即可