题意：在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动
时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移
动到某人心中的目标状态。
题解：状态数量最多2^16,算上转移的复杂度还是绰绰有余，可以直接bfs。
#include#include using namespace std; inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}return x*f; } const int dis[4][2]={ { 1,0},{-1,0},{ 0,-1},{ 0,1}}; const int p[4][4]={ { 1,2,4,8},{ 16,32,64,128},{ 256,512,1024,2048},{ 4096,8192,16384,32768}}; char s[4][4],s2[4][4]; int d[65537],to=0,beg=0; int q[600005],top=0,tail=0;inline bool check(int x,int a,int b){ return ((x&a)>0)==((x&b)>0);}void solve(int num,int x,int y) {int xx,yy,ans=d[num]+1;for(int i=0;i<4;i++){xx=x+dis[i][0];yy=y+dis[i][1];if(xx<0||yy<0||xx>=4||yy>=4||check(num,p[x][y],p[xx][yy]))continue;int t=num^p[x][y]^p[xx][yy];if(d[t]>ans){d[t]=ans;q[++top]=t;}} }int main() {for(int i=0;i<4;i++)scanf("%s",s[i]);for(int i=0;i<4;i++)scanf("%s",s2[i]);for(int i=0;i<4;i++)for(int j=0;j<4;j++)if(s2[i][j]=='1')to+=p[i][j];for(int i=0;i<4;i++)for(int j=0;j<4;j++)if(s[i][j]=='1')beg+=p[i][j];for(int i=0;i<65536;i++) d[i]=20000000;d[beg]=0;q[++top]=beg;while(top!=tail){int u=q[++tail];for(int i=0;i<4;i++)for(int j=0;j<4;j++)solve(u,i,j);}cout<<d[to];return 0; }