状压bfs

一共有16个位置，最多会有 \(2^{16}=65536\) 种情况，用数组完全开的下。
用二进制中的1表示该位置有玩具，0表示该位置没有玩具。
由于广搜最先搜到的是最优解，直接用数组记录是否到达过该状态，顺便记录ans.
移动前的状态ans为0.
然后大力讨论12种情况即可
时间复杂度O( \(2^{16}\) )O(能过)
献上我又臭又长的代码


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int z[524289],pan[524289];
int a,b,d;
char c;
queue<int>q;
int ex(int s,int li,int ri)
{
    return (s^(1<<li))^(1<<ri);
}
void fang(int xx,int fa)
{
    if(pan[xx]==0)
    {
        pan[xx]=1;
        z[xx]=z[fa]+1;
        q.push(xx);
    }
}
int main()
{
    //freopen("toy.in","r",stdin);
    //freopen("toy.out","w",stdout);
    for(int i=1;i<=16;++i)
    {
        cin>>c;
        a=(a<<1)|(c-'0');
    }
    for(int i=1;i<=16;++i)
    {
        cin>>c;
        b=(b<<1)|(c-'0');
    }
    if(a==b)
    {
        cout<<"0";
        return 0;
    }
    pan[a]=1;
    q.push(a);
    while(!q.empty())
    {
        int x=0;
        d=q.front();
        q.pop();
        if(d&(1<<15))//1号位 
        {
            if((d&(1<<14))==0)
            {
                x=ex(d,15,14);
                fang(x,d);
            }
            if((d&(1<<11))==0)
            {
                x=ex(d,15,11);
                fang(x,d);
            }
        }
        for(int i=2;i<=3;++i)//2~3号位 
        {
            if(d&(1<<(16-i)))
            {
                if((d&(1<<(16-i+1)))==0)
                {
                    x=ex(d,16-i,16-i+1);
                    fang(x,d);
                }
                if((d&(1<<(16-i-1)))==0)
                {
                    x=ex(d,16-i,16-i-1);
                    fang(x,d);
                }
                if((d&(1<<(16-i-4)))==0)
                {
                    x=ex(d,16-i,16-i-4);
                    fang(x,d);
                }
            }
        }
        if(d&(1<<12))//4号位 
        {
            if((d&(1<<13))==0)
            {
                x=ex(d,13,12);
                fang(x,d);
            }
            if((d&(1<<8))==0)
            {
                x=ex(d,12,8);
                fang(x,d);
            }
        }
        if(d&(1<<11))//5号位 
        {
            if((d&(1<<15))==0)
            {
                x=ex(d,15,11);
                fang(x,d);
            }
            if((d&(1<<10))==0)
            {
                x=ex(d,10,11);
                fang(x,d);
            }
            if((d&(1<<7))==0)
            {
                x=ex(d,7,11);
                fang(x,d);
            }
        }
        for(int i=6;i<=7;++i)//6~7号位 
        {
            if(d&(1<<(16-i)))
            {
                if((d&(1<<(16-i+4)))==0)
                {
                    x=ex(d,16-i,16-i+4);
                    fang(x,d);
                }
                if((d&(1<<(16-i+1)))==0)
                {
                    x=ex(d,16-i,16-i+1);
                    fang(x,d);
                }
                if((d&(1<<(16-i-1)))==0)
                {
                    x=ex(d,16-i,16-i-1);
                    fang(x,d);
                }
                if((d&(1<<(16-i-4)))==0)
                {
                    x=ex(d,16-i,16-i-4);
                    fang(x,d);
                }
            }
        }
        if(d&(1<<8))//8号位 
        {
            if((d&(1<<12))==0)
            {
                x=ex(d,8,12);
                fang(x,d);
            }
            if((d&(1<<9))==0)
            {
                x=ex(d,8,9);
                fang(x,d);
            }
            if((d&(1<<4))==0)
            {
                x=ex(d,8,4);
                fang(x,d);
            }
        }
        if(d&(1<<7))//9号位 
        {
            if((d&(1<<11))==0)
            {
                x=ex(d,7,11);
                fang(x,d);
            }
            if((d&(1<<6))==0)
            {
                x=ex(d,7,6);
                fang(x,d);
            }
            if((d&(1<<3))==0)
            {
                x=ex(d,7,3);
                fang(x,d);
            }
        }
        for(int i=10;i<=11;++i)//10~11号位 
        {
            if(d&(1<<(16-i)))
            {
                if((d&(1<<(16-i+4)))==0)
                {
                    x=ex(d,16-i,16-i+4);
                    fang(x,d);
                }
                if((d&(1<<(16-i+1)))==0)
                {
                    x=ex(d,16-i,16-i+1);
                    fang(x,d);
                }
                if((d&(1<<(16-i-1)))==0)
                {
                    x=ex(d,16-i,16-i-1);
                    fang(x,d);
                }
                if((d&(1<<(16-i-4)))==0)
                {
                    x=ex(d,16-i,16-i-4);
                    fang(x,d);
                }
            }
        }
        if(d&(1<<4))//12号位 
        {
            if((d&(1<<8))==0)
            {
                x=ex(d,8,4);
                fang(x,d);
            }
            if((d&(1<<5))==0)
            {
                x=ex(d,4,5);
                fang(x,d);
            }
            if((d&(1<<0))==0)
            {
                x=ex(d,4,0);
                fang(x,d);
            }
        }
        if(d&(1<<3))//13号位 
        {
            if((d&(1<<7))==0)
            {
                x=ex(d,3,7);
                fang(x,d);
            }
            if((d&(1<<2))==0)
            {
                x=ex(d,3,2);
                fang(x,d);
            }
        }
        for(int i=14;i<=15;++i)//14~15号位 
        {
            if(d&(1<<(16-i)))
            {
                if((d&(1<<(16-i+4)))==0)
                {
                    x=ex(d,16-i,16-i+4);
                    fang(x,d);
                }
                if((d&(1<<(16-i+1)))==0)
                {
                    x=ex(d,16-i,16-i+1);
                    fang(x,d);
                }
                if((d&(1<<(16-i-1)))==0)
                {
                    x=ex(d,16-i,16-i-1);
                    fang(x,d);
                }
            }
        }
        if(d&(1<<0))//16号位 
        {
            if((d&(1<<1))==0)
            {
                x=ex(d,0,1);
                fang(x,d);
            }
            if((d&(1<<4))==0)
            {
                x=ex(d,4,0);
                fang(x,d);
            }
        }
    }
    cout<<z[b];
    fclose(stdin);fclose(stdout);
    return 0;
}