首先是关于把数码问题状态转移的想法：我的想法是直接-1左,1右,-3上,3下,不巧的是wa了，为什么？因为在最左边的时候可能-1之后是在合理范围内的，但是显然不能够这样移动，比如3->2(下标从零开始);同样在最右边时候不能够再右移。
这个问题我解决了。但有个问题是我一直不是很能想明白的，就是这种问题怎么想到BFS能求解的，先求解后验证吗？还有没有什么其他方法能解决这题了呢？
我一开始不明白怎么去判断无解，以为可能存在某些状态会一直走下去（在有限时间内），结果我枚举了一下状态，一共也就362880种状态，再加上得到的结论，对于任意一种状态，去重之后最多可以到达181440种状态，这样的情况下显然我们是能够ac的。
这个问题的证明基于这样一个结论：不包括x在内的序列的逆序数就行如果相同，那么他们可以互达。（易证明）

问题链接及代码如下：
https://www.acwing.com/problem/content/847/

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<unordered_map>
#include<queue>
#include<algorithm>

using namespace std;

queue<string> state;
unordered_map<string,int> dist;
int change[4]={-1,1,-3,3};

int bfs(string st)
{
    string target="12345678x";//目标状态

    state.push(st);
    dist[st]=0;

    int x,y,distance;

    while(state.size())
    {
        string head=state.front();
        state.pop();

        if(head==target) return dist[head];

        distance=dist[head];

        x=head.find('x');

        for(int i=0;i<4;i++)
        {
            if(x%3==0 && change[i]==-1)continue;//如果当前处于最左边那就不能再往左走了
            if(x%3==2 && change[i]==1)continue;//如果当前处于最右边那就不能再往右走了
            y=change[i]+x;
            if(y>=0 && y<=8)//转移过去的状态是否合法
            {
                swap(head[x],head[y]);
                if(dist.find(head)==dist.end())//该状态是否在之前已经可以到达
                {
                    state.push(head);
                    dist[head]=distance+1;
                }
                swap(head[x],head[y]);
            }
        }
    }

    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string st;
    char t;
    for(int i=0;i<9;i++)cin>>t,st+=t;

    cout<<bfs(st)<<endl;
    return 0;
}