题目链接

题目描述

在一个3×3的网格中，1~8这8个数字和一个“X”恰好不重不漏地分布在这3×3的网格中。

例如：

1 2 3
X 4 6
7 5 8
在游戏过程中，可以把“X”与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 X
例如，示例中图形就可以通过让“X”先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3 1 2 3 1 2 3 1 2 3
X 4 6 4 X 6 4 5 6 4 5 6
7 5 8 7 5 8 7 X 8 7 8 X
把“X”与上下左右方向数字交换的行动记录为“u”、“d”、“l”、“r”。

现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

输入格式
输入占一行，将3×3的初始网格描绘出来。

例如，如果初始网格如下所示：
1 2 3

x 4 6

7 5 8

则输入为：1 2 3 x 4 6 7 5 8

输出格式
输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。
如果不存在解决方案，则输出”unsolvable”。

样例

输入样例：
2  3  4  1  5  x  7  6  8 
输出样例
ullddrurdllurdruldr

思路

(Astar) $O(不会算)$

此题将整个矩阵视为状态，然后以各点位置与目标状态位置的曼哈顿距离之和作为估价函数
我用康托展开哈希，如果状态出现过就$continue$
关于$A*$

Code

#include<bits/stdc++.h>
using namespace std;
int arr[10],vis[10],A[10],fac[10],a[10],L[10],R[10],ans,n;
bool flag[10000010];
char ip;
struct node
{
    int h[10],d,f;
    vector<int>pre;
    bool operator < (const node &x)const
    {
        return x.d+x.f<d+f;
    }
};
int C_hash()//Cantor Expansion
{
    int res=0,sum=0;
    for(int i=1;i<9;i++)
    {
        for(int j=i+1;j<=9;j++)
        {
            if(arr[j]<arr[i])
            {
                sum++;
            }
        }
        res+=sum*fac[9-i];
        sum=0;
    }
    return res+1;
}
int calc()
{
    int ans=0;
    for(int i=1;i<=9;i++)
    {
        if(arr[i]==9)
        {
            continue;
        }
        ans+=abs(((i-1)%3+1)-((arr[i]-1)%3+1))+abs(((i-1)/3+1)-((arr[i]-1)/3+1));
    }
    return ans;
}
priority_queue<node>q;
void Astar()
{
    while(!q.empty())
    {
        node T=q.top();
        int D=q.top().d;
        int F=q.top().f;
        q.pop();
        for(int i=1;i<=9;i++)
        {
            arr[i]=T.h[i];
        }
        int HASH=C_hash();
        if(flag[HASH])
        {
            continue;
        }
        else
        {
            flag[HASH]=1;
        }
        if(!calc())
        {
            for(int i=0;i<T.pre.size();i++)
            {
                if(T.pre[i]==1)
                {
                    cout<<"u";
                }
                if(T.pre[i]==2)
                {
                    cout<<"d";
                }
                if(T.pre[i]==3)
                {
                    cout<<"l";
                }
                if(T.pre[i]==4)
                {
                    cout<<"r";
                }
            }
            return ;
        }
        int X;
        for(int i=1;i<=9;i++)
        {
            if(arr[i]==9)
            {
                X=i;
                break;
            }
        }
        if(X>3)
        {
            swap(T.h[X],T.h[X-3]);
            T.f=calc();
            T.d=D+1;
            T.pre.push_back(1);
            q.push(T);
            T.pre.pop_back();
            swap(T.h[X],T.h[X-3]);
        }
        if(X<7)
        {
            swap(T.h[X],T.h[X+3]);
            T.f=calc();
            T.d=D+1;
            T.pre.push_back(2);
            q.push(T);
            T.pre.pop_back();
            swap(T.h[X],T.h[X+3]);
        }
        if((X-1)%3+1>1)
        {
            swap(T.h[X],T.h[X-1]);
            T.f=calc();
            T.d=D+1;
            T.pre.push_back(3);
            q.push(T);
            T.pre.pop_back();
            swap(T.h[X],T.h[X-1]);
        }
        if((X-1)%3+1<3)
        {
            swap(T.h[X],T.h[X+1]);
            T.f=calc();
            T.d=D+1;
            T.pre.push_back(4);
            q.push(T);
            T.pre.pop_back();
            swap(T.h[X],T.h[X+1]);
        }
    }
}
int mergesort(int l,int mid,int r)
{
    int n1,n2;
    n1=mid-l+1;
    n2=r-mid;
    for(int i=1;i<=n1;i++)
    {
        L[i]=a[i+l-1];
    }
    for(int i=1;i<=n2;i++)
    {
        R[i]=a[mid+i];
    }
    L[n1+1]=-999999999;
    R[n2+1]=-999999999;
    int q1=1,q2=1;
    for(;q2<=n2;)
    {
        if(L[q1]>R[q2])
        {
            ans+=n2-q2+1;
            q1++;
        }
        else
        {           
            q2++;
        }
    }
    q1=1,q2=1;
    for(int i=l;i<=r;i++)
    {
        if(L[q1]>=R[q2])
        {
            a[i]=L[q1];
            q1++;
        }
        else
        {
            a[i]=R[q2];
            q2++;
        }
    }   
}
int merge(int l,int r)
{
    if(l<r)
    {
        int mid=(l+r)/2;
        merge(l,mid);
        merge(mid+1,r);
        mergesort(l,mid,r);
    }
    return 0;
}
int main()
{
    fac[0]=1;
    for(int i=1;i<=9;i++)
    {
        fac[i]=fac[i-1]*i;
    }
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            cin>>ip;
            if('1'<=ip&&ip<='8')
            {
                arr[(i-1)*3+j]=ip-'0';
            }
            else
            {
                arr[(i-1)*3+j]=9;
            }
        }
    }
    for(int i=1;i<=9;i++)
    {
        if(arr[i]!=9)
        {
            a[++n]=arr[i];
        }
    }
    merge(1,n);
    int mod1=ans%2;
    ans=0;
    n=0;
    for(int i=1;i<=8;i++)
    {
        a[i]=i;
    }
    merge(1,n);
    int mod2=ans%2;
    if(mod1!=mod2)
    {
        cout<<"unsolvable";
        return 0;
    }
    node T;
    for(int i=1;i<=9;i++)
    {
        T.h[i]=arr[i];
    }
    T.d=0;
    T.f=calc();
    q.push(T);
    Astar();
}