2.八数码二(IDA*)

原题链接：https://www.acwing.com/problem/content/4231/

//IDA*
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<queue>
#include<cmath>
using namespace std;

#define x first
#define y second
typedef pair<int,string> PIS;
char op[4]={'d','l','r','u'};
int dx[4]={1,0,0,-1},dy[4]={0,-1,1,0};
int pos[10];//pos记录每一个数字在ed中的下标
int path[101000];
string st,ed;

int f()
{
    int res=0;
    for(int i=0;i<9;i++)
    {
        if(st[i]!='X')
        {
            int a=st[i]-'0';
            res+=abs(i/3-pos[a]/3)+abs(i%3-pos[a]%3);
        }
    }
    return res;
}

bool dfs(int k,int depth)
{
    if(k+f()>depth) return false;
    if(st==ed) return true;
    int x1,y1;
    for(int i=0;i<9;i++)
        if(st[i]=='X') x1=i/3,y1=i%3; 
    string last=st;
    for(int i=0;i<4;i++)
    {
        int x=dx[i]+x1,y=dy[i]+y1;
        //重要剪枝，避免往回走
        if(k>=1&&i+path[k-1]==3) continue;
        if(x<0||x>=3||y<0||y>=3) continue;
        swap(st[x1*3+y1],st[x*3+y]);
        path[k]=i;
        if(dfs(k+1,depth)) return true;
        swap(st[x1*3+y1],st[x*3+y]);
    }
    return false;
}

int main()
{
    int tt;
    cin>>tt;
    for(int i=1;i<=tt;i++)
    {
        cin>>st>>ed;
        string s=st;
        for(int j=0;j<9;j++){
            if(ed[j]!='X'){
                int a=ed[j]-'0';
                pos[a]=j;
            }
        }
        int depth=0;
        while(!dfs(0,depth)) depth++;
        printf("Case %d: %d\n",i,depth);
        for(int i=0;i<depth;i++) cout<<op[path[i]];
        cout<<endl;
    }
    
    return 0;
}