题目链接:
题意:八数码类似的题目,数字华容道,但是不同点在于格子可以上下左右移动,并且越界移动可以从另一边出来,并且横纵移动有不同的花费
解题思路:简单bfs啊!现在竟然还有一点点的觉得有很多题都是算法题,是自己能力范围之外的,其实不然,比如这一题就是一道简单bfs外加上unordered_map维护一下就够了呐,(其实本质上就是hash)
另外还有一种标记方式为康托展开,下一篇详细描述一下。


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll sc,vc;


struct node
{
    int a[10],pos;
    ll cost;
    ll now;
    friend bool operator <(node a,node b)
    {
        return a.cost>b.cost;
    }
};
//bool cmp(node a,node b)
//{
// return a.cost<b.cost;
//}
priority_queue<node>Q;

node enl(node a,int p,int cost)
{
    node ans;
    int tem=a.a[p];
    for(int i=0;i<9;i++)
    {
        ans.a[i]=a.a[i];
    }
    ans.a[p]=0;
    ans.a[a.pos]=tem;
    ll lin=0;
    for(int i=0;i<9;i++)
    {
        lin=lin*10+(ll)ans.a[i];
    }
    ans.now=lin;
    ans.cost=a.cost+cost;
    ans.pos=p;
    return ans;
}

int main()
{

// ios::sync_with_stdio(false);
// cout.tie(NULL);
    while(cin>>sc>>vc)
    {
        if(sc==0&&vc==0)break;
        unordered_map<ll,bool>mp;
        while(!Q.empty())Q.pop();
        int st[10];ll lin=0;
        int et[10];ll fin=0;
        for(int i=0;i<9;i++)
        {
            cin>>st[i];
            lin=lin*10+(ll)st[i];
        }

        for(int i=0;i<9;i++)
        {
            cin>>et[i];
            fin=fin*10+(ll)et[i];
        }
        node ss;
        for(int i=0;i<9;i++)
        {
            ss.a[i]=st[i];
            if(st[i]==0)ss.pos=i;
        }
        ss.now=lin;
        ss.cost=0;
        Q.push(ss);
        ll ans=0;
        while(!Q.empty())
        {
            node temp=Q.top();
// cout<<temp.now<<endl;
// for(int i=0;i<9;i++)
// cout<<temp.a[i]<<" ";
// cout<<endl;
            Q.pop();
            if(temp.now==fin)
            {
                ans=temp.cost;
                break;
            }
            if(mp.count(temp.now))continue;
            mp[temp.now]=1;
            node A=enl(temp,(temp.pos+1)%9,sc);
            Q.push(A);
            node B=enl(temp,(temp.pos-1+9)%9,sc);
            Q.push(B);
            node C=enl(temp,(temp.pos+3)%9,vc);
            Q.push(C);
            node D=enl(temp,(temp.pos-3+9*9)%9,vc);
            Q.push(D);

        }
        cout<<ans<<endl;

    }
    return 0;
}