acwing845. 八数码

#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<queue>
using namespace std;

int bfs(string state){
    queue<string> q;
    unordered_map<string,int> um;//存储每个状态所需的步数
    q.push(state);
    um[state]=0;
    string end="12345678x";
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};//移动方向
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        if(t==end){
            return um[t];
        }
        int distance=um[t];
        int k=t.find('x');
        int x=k/3,y=k%3;
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];//计算移动的下一个状态
            if(a>=0&&a<3&&b>=0&&b<3){
                swap(t[k],t[3*a+b]);
                if(!um.count(t)){
                    um[t]=distance+1;
                    q.push(t);
                }
                swap(t[k],t[3*a+b]);//恢复上一次
            }
        }
        
    }
    return -1;
    
}
int main(){
    char s[2];
    string start;
    for(int i=0;i<9;i++){
        cin>>s;
        start+=*s;
    }
    cout<<bfs(start)<<endl;
    
    return 0;
}