八数码难题

广搜 1（数字上操作）

#include <bits/stdc++.h>
using namespace std;
int n;
int ten[10];
map<int, int> dis;
queue<int> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    ten[0] = 1;
    for (int i = 1; i <= 8; i++)
        ten[i] = ten[i - 1] * 10;
    q.push(n);
    dis[n] = 0;
    while (!q.empty() &&
           dis.find(123804765) == dis.end())
    {
        int now = q.front();
        q.pop();
        // 0 的位置、目标的位置
        int pos = -1, t;
        for (int i = 0; i <= 8; i++)
            if (now / ten[i] % 10 == 0)
            {
                pos = i;
                break;
            }
        // 上下左右
        for (int i = 1; i <= 4; i++)
        {
            if (i == 1)
                t = pos - 3;
            if (i == 2)
                t = pos + 3;
            if (i == 3)
            {
                if (pos % 3 == 0)
                    t = -1;
                else
                    t = pos - 1;
            }
            if (i == 4)
            {
                if (pos % 3 == 2)
                    t = -1;
                else
                    t = pos + 1;
            }
            if (0 <= t && t <= 8)
            {
                // pos 上是 0，t 上是 x
                int x = now / ten[t] % 10;
                int nxt = now - x * ten[t] + x * ten[pos];
                if (dis.find(nxt) == dis.end())
                {
                    dis[nxt] = dis[now] + 1;
                    q.push(nxt);
                }
            }
        }
    }
    cout << dis[123804765];
    return 0;
}

广搜 2（真的展开九宫格）

#include <bits/stdc++.h>
using namespace std;
const int ed = 123804765;
map<int, int> dis;
queue<int> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int st;
    cin >> st;
    q.push(st);
    dis[st] = 1;
    while (!q.empty() && dis[ed] == 0)
    {
        int now = q.front();
        q.pop();
        /*
            d[0][0] d[0][1] d[0][2]
            d[1][0] d[1][1] d[1][2]
            d[2][0] d[2][1] d[2][2]
        */
        int d[3][3];
        d[0][0] = now / 100000000 % 10;
        d[0][1] = now / 10000000 % 10;
        d[0][2] = now / 1000000 % 10;
        d[1][0] = now / 100000 % 10;
        d[1][1] = now / 10000 % 10;
        d[1][2] = now / 1000 % 10;
        d[2][0] = now / 100 % 10;
        d[2][1] = now / 10 % 10;
        d[2][2] = now / 1 % 10;
        int x, y;
        for (int i = 0; i <= 2; i++)
            for (int j = 0; j <= 2; j++)
                if (d[i][j] == 0)
                    x = i, y = j;
        if (x != 0)
        {
            swap(d[x][y], d[x - 1][y]);
            int nxt = 0;
            for (int i = 0; i <= 2; i++)
                for (int j = 0; j <= 2; j++)
                    nxt = nxt * 10 + d[i][j];
            if (dis[nxt] == 0)
            {
                dis[nxt] = dis[now] + 1;
                q.push(nxt);
            }
            swap(d[x][y], d[x - 1][y]);
        }
        if (x != 2)
        {
            swap(d[x][y], d[x + 1][y]);
            int nxt = 0;
            for (int i = 0; i <= 2; i++)
                for (int j = 0; j <= 2; j++)
                    nxt = nxt * 10 + d[i][j];
            if (dis[nxt] == 0)
            {
                dis[nxt] = dis[now] + 1;
                q.push(nxt);
            }
            swap(d[x][y], d[x + 1][y]);
        }
        if (y != 0)
        {
            swap(d[x][y], d[x][y - 1]);
            int nxt = 0;
            for (int i = 0; i <= 2; i++)
                for (int j = 0; j <= 2; j++)
                    nxt = nxt * 10 + d[i][j];
            if (dis[nxt] == 0)
            {
                dis[nxt] = dis[now] + 1;
                q.push(nxt);
            }
            swap(d[x][y], d[x][y - 1]);
        }
        if (y != 2)
        {
            swap(d[x][y], d[x][y + 1]);
            int nxt = 0;
            for (int i = 0; i <= 2; i++)
                for (int j = 0; j <= 2; j++)
                    nxt = nxt * 10 + d[i][j];
            if (dis[nxt] == 0)
            {
                dis[nxt] = dis[now] + 1;
                q.push(nxt);
            }
            swap(d[x][y], d[x][y + 1]);
        }
    }
    cout << dis[ed] - 1;
    return 0;
}