[HAOI2008][BZOJ1054] 移动玩具

浏览数：32 / 时间：2015年06月11日

1054: [HAOI2008]移动玩具

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1277 Solved: 695
[Submit][Status][Discuss]

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

直觉是双向BFS，但是不会写。于是就看了题解，第一次见这样写BFS，感觉好巧妙啊。

数据规模小，但情况种类还是不少的。加上Hash判重（也是才学的），28MS AC。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int t,w,x,y,h,st,en;
bool ans[5][5];
bool flag,mark[66666];
char c;
struct node 
{
    bool a[5][5];
    int step;
};
node q[66666];
const int dx[5]={0,-1,0,1,0};
const int dy[5]={0,0,1,0,-1};
int hash(bool a[5][5])
{
    int k=1,s=0;
    for (int i=1;i<=4;i++)
        for (int j=1;j<=4;j++)
        {
            s+=k*a[i][j];
            k<<=1;
        }
    return s;
}
int main()
{
    memset(mark,0,sizeof(mark));
    for (int i=1;i<=4;i++)
    {
        for (int j=1;j<=4;j++)
        {
            c=getchar();
            q[1].a[i][j]=c-‘0‘;
        }
        getchar();
    }
    getchar();
    for (int i=1;i<=4;i++)
    {
        for (int j=1;j<=4;j++)
        {
            c=getchar();
            ans[i][j]=c-‘0‘;
        }
        getchar();
    }
    st=hash(q[1].a);
    en=hash(ans);
    if (st==en) { printf("0"); return 0; }
    mark[st]=1;
    t=0; w=1; q[1].step=0;
    while (t<w)
    {
        t++;
        for (int i=1;i<=4;i++)
            for (int j=1;j<=4;j++)
                if (q[t].a[i][j])
                    for (int k=1;k<=4;k++)
                    {  
                        x=i+dx[k];
                        y=j+dy[k];
                        if (x>4||y>4||x<1||y<1||q[t].a[x][y]) continue;
                        swap(q[t].a[i][j],q[t].a[x][y]);
                        h=hash(q[t].a);
                        if (!mark[h]) 
                        {
                                    if (h==en) { printf("%d",q[t].step+1); return 0; }
                                    w++;
                                    memcpy(q[w].a,q[t].a,sizeof(q[w].a));
                                    q[w].step=q[t].step+1;
                                    mark[h]=true;
                        }
                        swap(q[t].a[i][j],q[t].a[x][y]);
                    }
    }
    return 0;
}