八数码问题

#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <cstring>
#include <queue>

using namespace std;

int dfs(string start)
{
    string end = "12345678x";
    queue<string> q;
    unordered_map<string, int> d;
    q.push(start);
    d[start] = 0;
    int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
    
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int dis = d[t];
        if(t == end) return dis;
        int k = t.find(‘x‘);
        int x = k / 3,y = k % 3;
        for(int i = 0; i <= 3 ; i ++)
        {
            int nx = x + dx[i],ny = y + dy[i];
            if(nx >= 0 && nx <= 2 && ny >= 0 && ny <= 2)
            {
                swap(t[k],t[nx*3 + ny]);
                if(!d[t])
                {
                    d[t] = dis + 1;
                    q.push(t);
                }
                swap(t[k],t[nx*3 + ny]);
            }
        }
    }
    return -1;
}


int main()
{
    string start;
    for(int i = 0; i <= 8 ; i ++)
    {
        char c;
        cin >> c;
        start += c;
    }
    cout << dfs(start) << endl;

    return 0;
}

难点在于怎么表示状态,这里利用unordered_map处理问题,也可以利用康托展开处理问题

康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。
康托展开可以得到一个1~n的任意排列字典序排名,将其映射到哈希表上,可以用来表示当前状态有没有出现过.

八数码以及康托展开