【题目链接】:http://hihocoder.com/problemset/problem/1312?sid=1092363

【题意】

【题解】



定义一个A*函数

f = step+val

这里的val是当前这个状态;每个点到目标状态的点的曼哈顿距离的绝对值;

(这个值肯定比真正需要花费的路程短)

step就为当前状态花费的步数;

把普通队列改成优先队列;

优先处理f值小的状态;

f值相同的,优先处理step值小的;

(也就是说f值大的不是不处理了,而是放到后面再处理)

这样就能较快地逼近目标状态了;

效果异常地棒

2s变成0.2s了!



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const int pre[9][2] =

{

    {2,2},

    {0,0},{0,1},{0,2},

    {1,0},{1,1},{1,2},

    {2,0},{2,1}

};

const double pi = acos(-1.0);

const int N = 110;

struct node

{

    int a[9],p,step,f;

    friend bool operator < (node x,node y)

    {

        if (x.f==y.f)

        {

            if (x.step==y.step)

                return true;

            else

                return x.step>y.step;

        }

        else

            return x.f>y.f;

    }

};

node init;

priority_queue <node> dl;

map <int,int> dic;

int a[9],goal;

int cs[9] = {1,2,3,4,5,6,7,8,0};

int has(int *a)

{

    int x = 0;

    rep1(i,0,8) x = x*10 + a[i];

    return x;

}

int val(int *a)

{

    int ret = 0;

    rep1(i,0,8)

    {

        int x = i/3,y = i%3;

        if (a[i]==0) continue;

        ret+=abs(pre[a[i]][0]-x)+abs(pre[a[i]][1]-y);

    }

    return ret;

}

int bfs()

{

    while (!dl.empty())

    {

        int p = dl.top().p;

        int now = dl.top().step;

        node temp;

        rep1(i,0,8) temp.a[i] = dl.top().a[i];

        dl.pop();

        //上

        if (p>2)

        {

            int tp = p-3;

            swap(temp.a[tp],temp.a[p]);

            int xzt = has(temp.a);

            if (xzt==goal) return now+1;

            if (dic.find(xzt)==dic.end())

            {

                dic[xzt] = now+1;

                temp.step = now+1;

                temp.p = tp;

                temp.f = temp.step+val(temp.a);

                dl.push(temp);

            }

            swap(temp.a[tp],temp.a[p]);

        }

        //下

        if (p<6)

        {

            int tp = p+3;

            swap(temp.a[tp],temp.a[p]);

            int xzt = has(temp.a);

            if (xzt==goal) return now+1;

            if (dic.find(xzt)==dic.end())

            {

                dic[xzt] = now+1;

                temp.step = now+1;

                temp.p = tp;

                temp.f = temp.step+val(temp.a);

                dl.push(temp);

            }

            swap(temp.a[tp],temp.a[p]);

        }

        //左

        if (p%3!=0)

        {

            int tp = p-1;

            swap(temp.a[tp],temp.a[p]);

            int xzt = has(temp.a);

            if (xzt==goal) return now+1;

            if (dic.find(xzt)==dic.end())

            {

                dic[xzt] = now+1;

                temp.step = now+1;

                temp.p = tp;

                temp.f = temp.step+val(temp.a);

                dl.push(temp);

            }

            swap(temp.a[tp],temp.a[p]);

        }

        //右

        if (p%3!=2)

        {

            int tp = p+1;

            swap(temp.a[tp],temp.a[p]);

            int xzt = has(temp.a);

            if (xzt==goal) return now+1;

            if (dic.find(xzt)==dic.end())

            {

                dic[xzt] = now+1;

                temp.step = now+1;

                temp.p = tp;

                temp.f = temp.step+val(temp.a);

                dl.push(temp);

            }

            swap(temp.a[tp],temp.a[p]);

        }

    }

    return -1;

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use

    goal = has(cs);

    int t;

    cin >> t;

    while (t--)

    {

        dic.clear();

        rep1(i,0,8)

        {

            cin >> a[i];

            if (a[i]==0) init.p = i;

        }

        rep1(i,0,8) init.a[i] = a[i];

        init.step = 0,init.f = init.step+val(init.a);

        dic[has(init.a)] = 0;

        if (has(init.a)==goal)

        {

            cout << 0 << endl;

            continue;

        }

        while (!dl.empty()) dl.pop();

        dl.push(init);

        int ans = bfs();

        if (ans==-1)

            cout <<"No Solution!"<<endl;

        else

            cout << ans << endl;

    }

    return 0;

}