八数码

acwing845

inline bool check(int x,int y)
{
    return x>=0 && x<3 && y>=0 && y<3;
}

void print(string s)
{
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
            cout<<s[i*3+j]<<' ';
        cout<<endl;
    }
    cout<<endl;
}

int bfs(string s)
{
    queue<string> q;
    unordered_map<string,int> dist;
    dist[s]=0;
    q.push(s);

    while(q.size())
    {
        string t=q.front();
        q.pop();
        
       // print(t);
        
        if(t == "12345678x") return dist[t];
        
        int pos=t.find('x');
        int x=pos/3,y=pos%3;

        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(!check(a,b)) continue;
            int npos=a*3+b;
            string str=t;
            swap(str[pos],str[npos]);
            if(!dist.count(str))
            {
                dist[str]=dist[t]+1;
                q.push(str);
            }
        }
    }
    return -1;
}

int main()
{
    string line;
    getline(cin,line);
    stringstream ss(line);

    string a;
    char c;
    while(ss>>c) a+=c;

    cout<<bfs(a)<<endl;

    //system("pause");
}