BFS

#include <bits/stdc++.h>
using namespace std;

typedef pair<string, int> PSI;
#define fi first
#define se second

const int N=3;
int dirs[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
string G;
queue<PSI> q;
unordered_set<string> REC;
string final="12345678x";


int bfs(){
    if(G==final) return 0;
    q.push({G, 0});
    REC.insert(G);
    while(!q.empty()){
        string state = q.front().fi;
        int step = q.front().se;
        q.pop();
        // 定位x的坐标
        int pos=0;
        for(pos=0; pos<(int)state.size(); ++pos){
            if(state[pos]=='x')
                break;
        }
        int x=pos/N;
        int y=pos%N;

        for(auto& dir:dirs){
            int nx=x+dir[0];
            int ny=y+dir[1];
            if(0<=nx && nx<N && 0<=ny && ny<N){
                string new_state(state);
                int t=state[pos];
                new_state[pos]=state[nx*N+ny];
                new_state[nx*N+ny]=t;
                if(new_state==final) return step+1;
                if(REC.find(new_state)==REC.end()){
                    REC.insert(new_state);
                    q.push({new_state, step+1});
                }
            }
        }
    }
    return -1;
}



int main(){

    char g;
    for(int i=0; i<N*N; ++i){
        cin>>g;
        G+=g;
    }
    cout<<bfs()<<endl;

    return 0;
}

BFS代码优化

#include <bits/stdc++.h>
using namespace std;

typedef pair<string, int> PSI;
#define fi first
#define se second

const int N=3;
int dirs[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
string G;
queue<PSI> q;
unordered_set<string> REC;
string final="12345678x";


int bfs(){
    if(G==final) return 0;
    q.push({G, 0});
    REC.insert(G);
    while(!q.empty()){
        string state = q.front().fi;
        int step = q.front().se;
        q.pop();
        // 定位x的坐标
        int pos=state.find('x');
        int x=pos/N;
        int y=pos%N;

        for(auto& dir:dirs){
            int nx=x+dir[0];
            int ny=y+dir[1];
            if(0<=nx && nx<N && 0<=ny && ny<N){
                swap(state[pos], state[nx*N+ny]);
                if(state==final) return step+1;
                if(REC.find(state)==REC.end()){
                    REC.insert(state);
                    q.push({state, step+1});
                }
                swap(state[pos], state[nx*N+ny]);
            }
        }
    }
    return -1;
}

int main(){

    char g;
    for(int i=0; i<N*N; ++i){
        cin>>g;
        G+=g;
    }
    cout<<bfs()<<endl;

    return 0;
}