lanqiao OJ 261 九宫重排

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
 
using namespace std ;
int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
queue<string> q ;//bfs
string a ,b;//初始字符串，目标字符串
map<string,int> mp ;//用mp记录距离，已经变换过的次数
 
int bfs(){
    while(!q.empty()){
        string now = q.front() ;
        q.pop() ;
        if(now == b) return mp[now] ;//找到目标字符串就返回
        int cnt1 = now.find('.') ;//找到‘.’在字符串的位置
        int x = cnt1 / 3 , y = cnt1 % 3 ;
        for(int i = 0 ; i < 4 ; i ++){
            int tx = x + d[i][0] , ty = y + d[i][1]  ;       
            if(tx<0||tx>=3||ty<0||ty>=3) continue ;
            int cnt2 = tx * 3 + ty ;  
            string ts = now ;
            ts[cnt1] = now[cnt2] ;
            ts[cnt2] = '.' ;
 
            if(mp[ts]) continue ;//如果这个字符串已经被遍历过就继续循环
 
            q.push(ts) ;
            mp[ts] = mp[now] + 1 ;//mp值加一
        }
    }
}
 
int main(){
    cin >> a >> b ;
    q.push(a) ;
    
    mp[a] = 0 ;//当初始状态的时候不用变换为0
    cout << bfs() << endl ;
    return 0 ;
}