试题 历届试题 九宫重排(bfs)

#include<bits/stdc++.h>
using namespace std;
struct situation{
    string str;
    int pos;
    int step;
    situation(string s,int n){
        str=s;
        step=n;
        pos=getpos();
    }
    int getpos(){
        for(int i=0;i<str.size();i++){
            if(str[i]==‘.‘){
                return i;
            }
        }
    }
};
int dic[9][4]={{1,3},{0,2,4},{1,5},{0,4,6},{1,3,5,7},{2,4,8},{3,7},{4,6,8},{5,7}};
int dnc[9]={2,3,2,3,4,3,2,3,2};
queue<situation>q;
set<string>ss;
void bfs(string first,string target){
    q.push(situation(first,0));
    while(!q.empty()){
        situation s=q.front();
        q.pop();
        string str=s.str;
        int now=s.step;
        int pos=s.pos;
        for(int i=0;i<dnc[pos];i++){
            swap(str[pos],str[dic[pos][i]]);
            if(str==target){
                cout<<now+1<<endl;
                return ;
            }
            if(!ss.count(str)){
                ss.insert(str);
                q.push(situation(str,now+1));
            }
            swap(str[pos],str[dic[pos][i]]);
        }
    }
}
int main(){
    string a,b;
    cin>>a>>b;
    bfs(a,b);
    return 0;
}