845. 八数码

题目链接https://www.acwing.com/problem/content/847/
题目：


思路：用map来进行判重 +计数操作，用queue来进行bfs，string里的find(x)函数返回的是x的下标

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<unordered_map>
using namespace std;
unordered_map<string ,int >st;
queue<string> q;
string s;
int fx1[4]={0,0,1,-1};
int fx2[4]={1,-1,0,0};
int solve(){
    q.push(s);
    st[s]=0;
    string ed="12345678x";
    while(q.size()){
        string t=q.front();
        q.pop();
        if(t==ed) return st[t];
        int k=t.find('x');
        int x=k/3,y=k%3;
        int ct=st[t];
        for(int i=0;i<4;i++){
            int r=x+fx1[i],c=y+fx2[i];
            if(r>=0&&r<3&&c>=0&&c<3){
                swap(t[r*3+c],t[k]);
                if(!st.count(t)){
                    st[t]=ct+1;
                    q.push(t);
                }
                swap(t[r*3+c],t[k]);
            }

        }
    }
    return -1;
}
int main(){
    char c;
    for(int i=0;i<9;i++){
        cin>>c;
        s+=c;
    }
    //cout<<s<<endl;
    cout<<solve();
    return 0;
}