[BZOJ 1054][HAOI 2008]移动玩具(BFS+判重)

题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1054

真是水题，感谢HAOI送的福利样例23333

裸BFS，用string做判重，会八数码就会这题。

注意由于队列中状态数很多，一定要把队列的数组开大点！！！

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <map>

#define MAXN 5

using namespace std;

map<string,bool>visit;

int tmp[MAXN][MAXN],nowstatus[MAXN][MAXN];
int xx[]={1,-1,0,0},yy[]={0,0,1,-1};

bool inMap(int x,int y)
{
    if(x<1||x>4||y<1||y>4) return false;
    return true;
}

string GetPermutationFromArray()
{
    string ans="";
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            ans+=tmp[i][j]+'0';
    return ans;
}

void GetArrayFromPermutaion(string s)
{
    int p=0;
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            tmp[i][j]=s[p++]-'0';
}

struct node
{
    string status;
    int step;
}q[100000],first,goal;

int h=0,t=0;

int BFS()
{
    q[t++]=first;
    visit[first.status]=true;
    while(h<t)
    {
        node now=q[h++];
        if(now.status==goal.status) return now.step;
        GetArrayFromPermutaion(now.status);
        for(int x=1;x<=4;x++)
            for(int y=1;y<=4;y++)
            {
                if(tmp[x][y]==1) //(x,y)是玩具
                {
                    for(int dir=0;dir<4;dir++)
                    {
                        int tx=x+xx[dir],ty=y+yy[dir];
                        if(!inMap(tx,ty)) continue;
                        if(tmp[tx][ty]==0) //(tx,ty)是空地
                        {
                            node next;
                            next.step=now.step+1;
                            swap(tmp[x][y],tmp[tx][ty]);
                            next.status=GetPermutationFromArray();
                            if(!visit[next.status])
                            {
                                visit[next.status]=true;
                                q[t++]=next;
                            }
                            swap(tmp[x][y],tmp[tx][ty]);
                        }
                    }
                }
            }
    }
    return -1;
}

int main()
{
    string s;
    first.step=0;
    for(int i=1;i<=4;i++)
    {
        cin>>s;
        first.status+=s;
    }
    for(int i=1;i<=4;i++)
    {
        cin>>s;
        goal.status+=s;
    }
    printf("%d\n",BFS());
    return 0;
}