Description
在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。
Input
前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。
Output
一个整数，所需要的最少移动次数。
Sample Input
1111
0000
1110
0010
1010
0101
1010
0101
Sample Output
4
题目分析
我们将4*4的矩阵看成16位的二进制数 然后跑bfs就可以啦
记得判重 不然TLE
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int a,b;
char s[22];
queue<int>q;
int dis[1<<17];
bool vis[1<<17];
int tmp,nmp;
void move(int x,int i)
{
if(x&(1<<i)) return ;
int y=x+(1<<i);
if(vis[y]) return ;
q.push(y),dis[y]=dis[nmp]+1,vis[y]=1;
return ;
}
void bfs()
{
q.push(a);
vis[a]=true;
while(q.size())
{
nmp=q.front();
q.pop();
for(int i=0;i<16;i++)
if(nmp&(1<<i))
{
tmp=(1<<i)^nmp;
if(i%4>0) move(tmp,i-1);
if(i%4<3) move(tmp,i+1);
if(i/4>0) move(tmp,i-4);
if(i/4<3) move(tmp,i+4);
if(vis[b])
{
printf("%d",dis[b]);
return ;
}
}
}
}
int main()
{
for(int i=1;i<=4;i++)
{
scanf("%s",&s[0]);
for(int j=0;j<4;j++)
{
a=a*2;
if(s[j]=='#') a++;
}
}
for(int i=1;i<=4;i++)
{
scanf("%s",&s[0]);
for(int j=0;j<4;j++)
{
b=b*2;
if(s[j]=='#') b++;
}
}
bfs();
return 0;
}
