C++的哈希表unordered_map实现

注意：需要C++11支持

• 记得要恢复现场，四个方向的改变要互不影响

其他解释的看视频即可，后面给出不使用C++11的康托解法！

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;
string start;
unordered_map<string, int> dist;
queue<string> q;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int bfs(){
    // 定义到全局变量冲突
    string end = "12345678x";

    q.push(start);
    dist[start] = 0;
    while(q.size()){
        auto t = q.front();
        q.pop();
        if(t == end) return dist[end];

        int distance = dist[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[a * 3 + b]);
                if(!dist.count(t)){
                    dist[t] = distance + 1;
                    q.push(t);
                }
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    return -1;
}

int main(){
    for(int i = 0; i < 9; i++){
        char c; cin >> c;
        start += c;
    }
    cout << bfs() << endl;
    return 0;
}

康托展开（解决不支持C++11）

资料参考：康托与逆康托展开

主要思想：（其实就是处理全排列的一种精妙的哈希手段！）通过康托展开可以将一个全排列映射到0 ~ n! - 1，对于本题就是9! - 1 = 362879种排列，只需要362879大小的数组即可存储下来所有状态！

康托展开：实现了计算按照字典序排列的顺序，例如12345对应的就是0

本题解只是通过康托展开将其映射到一个数字形成哈希表，初始状态初始化为-1，表示没有使用过即可！

对上一题的dist数组进行简单修改：dist[t] -> dist[cantor(t)]

目前没有用到逆康托展开，先不进行看了，用到再进行了解和学习！

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;
string start;
queue<string> q;
// 8*8! + 7*7! .... 0*0! = 9! - 1 = 362879
int dist[362880];
int fact[9];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

// x看作9即可，x ASKII码也比8大
// 康托展开
int cantor(string s){
    int res = 0;
    for(int i = 0; i < 9; i++){
        int d = 0;
        for(int j = i + 1; j < 9; j++)
            if(s[i] > s[j]) d ++;
        res += d * fact[9 - i - 1];
    }
    return res;
}

int bfs(){
    // 定义到全局变量冲突
    string end = "12345678x";

    q.push(start);
    dist[cantor(start)] = 0;
    while(q.size()){
        auto t = q.front();
        q.pop();
        if(t == end) return dist[cantor(end)];

        int distance = dist[cantor(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[a * 3 + b]);
                if(dist[cantor(t)] == -1){
                    dist[cantor(t)] = distance + 1;
                    q.push(t);
                }
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    return -1;
}

int main(){
    // -1表示没有使用过
    memset(dist, -1, sizeof dist);
    // 预处理i!
    fact[0] = 1;
    for(int i = 1; i < 9; i++) fact[i] = fact[i - 1] * i;

    for(int i = 0; i < 9; i++){
        char c; cin >> c;
        start += c;
    }
    cout << bfs() << endl;
    return 0;
}