【bzoj1054】[HAOI2008]移动玩具

2015.04.16 10:51 Thu | 5次阅读 | 旧日oi | 固定链接 | 源码

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

题解

bfs+hash判重,注意开始要特判状态相同

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 200010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
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;
}
char s[5];
struct queue{
    bool a[5][5];
    int step;
    int hash;
}q[maxn],st,ed,tmp;
int f,t,x,y;
bool mark[maxn];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int hash(bool a[5][5])
{
    int k=0;
    for(int i=1;i<=4;i++)
    for(int j=1;j<=4;j++)
    k=(k<<1)+a[i][j];
    return k;
}
int main()
{
    for(int i=1;i<=4;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<=4;j++)
        st.a[i][j]=s[j]-'0';
    }
    int hst=hash(st.a);
    mark[hst]=1;
    for(int i=1;i<=4;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<=4;j++)
        ed.a[i][j]=s[j]-'0';
    }
    int hed=hash(ed.a);
    if(hst==hed) 
    {
        puts("0");
        return 0;
    }
    q[t++]=st;
    while(f<t)
    {
        for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
        if(q[f].a[i][j])
        {
            for(int k=0;k<4;k++)
            {
                x=i+dx[k],y=j+dy[k];
                if(q[f].a[x][y]||x<1||x>4||y<1||y>4) continue;
                tmp=q[f];
                swap(tmp.a[i][j],tmp.a[x][y]);
                int h=hash(tmp.a);
                tmp.step=q[f].step+1;
                if(h==hed) 
                {
                    printf("%d\n",tmp.step);
                    return 0;
                }
                if(!mark[h])
                {
                    q[t++]=tmp;
                    mark[h]=1;
                }
            }
        }
        f++;
    }
}```