九宫重排

#include<iostream>
#include<map>
#include<string>
#include<queue>
#include<cstring>

using namespace std;

const int N = 400000;

#define state pair<int, int>
#define hash first
#define pos second 

int factor[10];

int step[N];
int st[N];

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int cantor(const string &s){
    int res = 0;
    for(int i = 0; i < s.size(); i ++){
        int cnt = 0;
        for(int j = i + 1; j < s.size(); j ++){
            if(s[j] < s[i]) cnt ++;
        }
        res += cnt * factor[8 - i];
    }
    return res;
}

string decantor(int hash){
    string t = ".12345678";
    int len = 9;
    string s;
    for(int i = 8; i >= 0; i --){
        int l = hash / factor[i];
        hash %= factor[i];
        s += t[l];
        for(int j = l + 1; j < len; j ++) t[j - 1] = t[j];
        len --;
    }
    return s;
}

int bfs(const state &s, int aim){
    queue<state> q;
    q.push(s);
    
    st[s.hash] = 1;
    
    while(q.size()){
        state h = q.front();
        q.pop();
        
        int x = h.pos / 3, y = h.pos % 3;
        string t = decantor(h.hash);
        
        for(int i = 0; i < 4; i ++){
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || b < 0 || a >= 3 || b >= 3) continue;
            int pos = a * 3 + b;
            swap(t[pos], t[h.pos]);
            int ct = cantor(t);
            swap(t[pos], t[h.pos]);
            if(st[ct]) continue;
            q.push({ct, pos});
            st[ct] = 1;
            step[ct] = step[h.hash] + 1;
            if(aim == ct) return step[ct];
        }
    }
    
    return -1;
}

void init(){
    factor[0] = 1;
    for(int i = 1; i < 10; i ++)
        factor[i] = factor[i - 1] * i;
}

int main(){
    init();
    
    string start, aim;
    cin >> start >> aim;
    
    int pos = 0;
    for(int i = 0; i < start.size(); i ++)
        if(start[i] == ‘.‘){
            pos = i;
            break;
        }
        
    cout << bfs({cantor(start), pos}, cantor(aim));
    return 0;
}

九宫重排

原文：https://www.cnblogs.com/tomori/p/13675093.html