poj1077 Eight【爆搜+Hash（脸题-_-b）】

转载请注明出处，谢谢：http://www.cnblogs.com/KirisameMarisa/p/4298840.html ---by 墨染之樱花

题目描述：民间流传的推15游戏，不过这里简化为3*3，也就是八数码问题，‘x’表示空位。与AOJ0121的“Seven Puzzle”类似。

思路：没什么特别的，构造字符串队列，爆搜一下。注意Hash函数，哈得好就哈哈，哈得不好就只能呵呵了。。。我的hash函数是∑((str[i]*7^i))%1000007外加在x的位置加上i*10007，547MS水过。不过在一样的题hdu1043时限变成了5秒却还是TLE了，果然此题杭电的数据更强，看来是要用A*了。

#include <iostream>

#include <ios>

#include <iomanip>

#include <functional>

#include <algorithm>

#include <vector>

#include <sstream>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <string>

#include <set>

#include <map>

#include <cstdio>

#include <cstdlib>

#include <cctype>

#include <cmath>

#include <cstring>

#include <climits>

using namespace std;

#define XINF INT_MAX

#define INF 1<<30

#define MAXN 1000007

#define eps 1e-10

#define zero(a) fabs(a)<eps

#define sqr(a) ((a)*(a))

#define MP(X,Y) make_pair(X,Y)

#define PB(X) push_back(X)

#define PF(X) push_front(X)

#define REP(X,N) for(int X=0;X<N;X++)

#define REP2(X,L,R) for(int X=L;X<=R;X++)

#define DEP(X,R,L) for(int X=R;X>=L;X--)

#define CLR(A,X) memset(A,X,sizeof(A))

#define IT iterator

#define PI  acos(-1.0)

#define test puts("OK");

#define _ ios_base::sync_with_stdio(0);cin.tie(0);

typedef long long ll;

typedef pair<int,int> PII;

typedef priority_queue<int,vector<int>,greater<int> > PQI;

typedef vector<PII> VII;

typedef vector<int> VI;

#define X first

#define Y second

inline int Hash(string str)

{

    int len=str.length(),s=,ans=;

    REP(i,len)

    {

        if(str[i]>='' && str[i]<='')

            ans+=(str[i]-'')*s;

        else

            ans+=i*;

        s*=;

        ans=ans%MAXN;

    }

    return ans;

}

pair<int,int> par[MAXN];

bool vis[MAXN];

int dir[][]={{-,},{,},{,},{,-}};

char direction[]={'u','d','r','l'};

char ans[+];

void bfs(string start,string end)

{

    CLR(vis,);

    queue<string> Q;

    int s=Hash(start);

    Q.push(start);

    vis[s]=;

    par[s]=MP(s,-);

    while(!Q.empty())

    {

        string temp=Q.front();Q.pop();

        if(temp==end)

            break;

        int pos;

        REP(i,)

            if(temp[i]=='x')

                pos=i;

        int x=pos/,y=pos%;

        REP(i,)

        {

            int tx=x+dir[i][],ty=y+dir[i][];

            if(tx>= && tx< && ty>= && ty<)

            {

                string next=temp;

                swap(next[tx*+ty],next[x*+y]);

                int ll=Hash(next);

                if(!vis[ll])

                {

                    par[ll]=MP(Hash(temp),i);

                    vis[ll]=;

                    Q.push(next);

                }

            }

        }

    }

}

int main()

{_

    string s="";

    REP(i,)

    {

        char c;

        cin>>c;

        s+=c;

    }

    bfs(s,"12345678x");

    int res=Hash("12345678x"),tot=;

    while(par[res].X!=res)

    {

        ans[tot++]=direction[par[res].Y];

        res=par[res].X;

    }

    for(int i=tot-;i>=;i--)

        cout<<ans[i];

    cout<<endl;

    return ;

}