【题目链接】:

【题意】

【题解】

从末状态的123456780开始逆向搜;

看它能到达哪些状态;

到时候O(1)输出就可以了;

用map< int,int> dic来判重;

对于状态;

用数组表示;

然后把它转化成一个对应的十进制数;

【Number Of WA】

0

【完整代码】

#include 
     
      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
      
        pii;typedef pair
       
         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 cs[9] = {
    1,2,3,4,5,6,7,8,0};const double pi = acos(-1.0);const int N = 110;struct node{    int a[9],p,step;};node init;queue 
        
          dl;map 
         
           dic;int a[9];int has(int a[9]){    int x = 0;    rep1(i,0,8)        x = x*10 + a[i];    return x;}int main(){    //freopen("F:\\rush.txt","r",stdin);    ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use    rep1(i,0,8) init.a[i] = cs[i];    init.p = 8,init.step = 0;    dl.push(init);    dic[has(init.a)] = 0;    while (!dl.empty())    {        int p = dl.front().p;        int now = dl.front().step;        node temp;        rep1(i,0,8) temp.a[i] = dl.front().a[i];        dl.pop();        //上        if (p>2)        {            int tp = p-3;            swap(temp.a[tp],temp.a[p]);            int xzt = has(temp.a);            if (dic.find(xzt)==dic.end())            {                dic[xzt] = now+1;                temp.step = now+1;                temp.p = tp;                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 (dic.find(xzt)==dic.end())            {                dic[xzt] = now+1;                temp.step = now+1;                temp.p = tp;                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 (dic.find(xzt)==dic.end())            {                dic[xzt] = now+1;                temp.step = now+1;                temp.p = tp;                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 (dic.find(xzt)==dic.end())            {                dic[xzt] = now+1;                temp.step = now+1;                temp.p = tp;                dl.push(temp);            }            swap(temp.a[tp],temp.a[p]);        }    }    int t;    cin >> t;    while (t--)    {        rep1(i,0,8)            cin >> a[i];        int zt = has(a);        if (dic.find(zt)!=dic.end())            cout << dic[zt] << endl;        else            cout << "No Solution!" << endl;    }    return 0;}