HDU - 3567
题意：
给两个九宫格，你只能让X和与X相邻的格子进行交换，请从状态a得到状态b，要求移动次数最少且答案的字典序最小
思路：
稍有难度的一道搜索，我们需要用到IDA* 算法（还有其他很多种方法，有兴趣的可以自行尝试，这里使用的是IDA* 进行解答）
利用A* 算法来得到最小的移动次数的期望值，然后利用ID算法来进行迭代加深，如果了解 IDA* 算法的话，这道题就是一道板子题
（注意：A* 算法得到的最小移动次数是小于等于实际次数的，不理解的话可以查阅一下关于A* 算法的资料）
代码附：
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
const int N = 2e5+10;
const int INF = 0x3f3f3f3f;
char dir[4]= {'d','l','r','u'};
int mov[4]= {3,-1,1,-3};
bool flag;
int a[11],b[11],pos[11],done[10000],deep,star;
string s1,s2;
int Astar()
{int h=0,now;for(int i=0; i<9; ++i){now=a[i];if(now){int row=pos[now]/3;int col=pos[now]%3;h=h+abs(row-i/3)+abs(col-(i%3));}}return h;
}
bool check()
{for(int i=0; i<9; ++i)if(a[i]!=b[i])return false;return true;
}
void IDAstar(int now,int pre,int step)
{if(flag)return ;if(check()){cout<<step<<endl;for(int i=0; i<step; ++i)cout<<dir[done[i]];cout<<endl;flag=1;return ;}int h=Astar();if(h+step>deep)return ;for(int i=0; i<4; ++i){if(i+pre==3)continue;int neww=now+mov[i];if(neww<0||neww>8||i==1&&(now%3==0)||i==2&&(now%3==2))continue;done[step]=i;swap(a[now],a[neww]);IDAstar(neww,i,step+1);swap(a[now],a[neww]);}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);int T;cin>>T;for(int t=1; t<=T; ++t){deep=0;flag=0;cin>>s1>>s2;cout<<"Case "<<t<<": ";memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(int i=0; i<9; ++i){if(s1[i]!='X')a[i]=s1[i]-'0';elsestar=i;}for(int i=0; i<9; ++i)if(s2[i]!='X'){b[i]=s2[i]-'0';pos[s2[i]-'0']=i;}while(!flag){IDAstar(star,10,0);deep++;}}return 0;
}