poj1077 Eight

题目链接: poj1077 Eight

难点在如何标记已遍历的的八数码状态：利用康托展开可将全排列一一映射到自然数。

解决状态标记问题，剩下的就与普通 \(bfs\) 无异了。

初始化从终态开始搜索，遍历八数码所有的状态。随后根据输入的状态直接回溯到终态。

/**
* poj1077 Eight
* 八数码的状态共有9!=362880种
*/

#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#include <string>
#include <stack>
#include <vector>
#include <map>
using namespace std;

const int N = 10, M = 4e5;
int puzzle[N];

struct node{int state[N], step; char op; int fa;} Q[M];
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};  // 上下左右
char ops[] = {‘d‘,‘u‘,‘r‘,‘l‘};  // 下上右左
bool vis[M];
int ans[M];

// 将全排列康托展开成自然数, 复杂度O(n^2)
int fac[10] = {1,1,2,6,24,120,720,5040,40320,362880};
int cantor(int*s, int n)
{
    int res = 0;
    for (int i = 0; i < n; ++i) {
        int cnt = 0;
        for (int j = i+1; j < n; ++j) if (s[j] < s[i]) ++cnt;
        res += cnt * fac[n-1-i];
    }
    return res;
}
void bfs()
{
    int head, tail;
    head = tail = 0;
    Q[tail++] = node{{1,2,3,4,5,6,7,8,9}, 0, ‘ ‘, -1};
    vis[0] = 1;
    while (head != tail) {
        node &t = Q[head];
        int id = cantor(t.state, 9);
        ans[id] = head;

        int pos = -1;
        for (pos = 0; pos < 9; ++pos) if(t.state[pos] == 9) break;
        int x = pos/3, y = pos%3;

        for (int i = 0; i < 4; ++i) {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (tx < 0 || tx > 2) continue;
            if (ty < 0 || ty > 2) continue;
            int tpos = tx*3+ty;
            node nxt = t;
            nxt.step += 1;
            nxt.op = ops[i];
            nxt.fa = head;

            // cout << pos << ‘#‘ << tpos << endl;
            swap(nxt.state[pos], nxt.state[tpos]);
            int id = cantor(nxt.state, 9);
            if (vis[id]) continue;
            Q[tail++] = nxt;
            vis[id] = 1;
        }

        ++head;
    }
}

int main()
{
    memset(ans, -1, sizeof ans);
    // 初始从终态搜索，记录所有状态
    bfs();


    for (int i = 0; i < 9; ++i) {
        char c;
        cin >> c;
        if (c == ‘x‘) c = ‘9‘;
        puzzle[i] = c ^ ‘0‘;
    }

    int id = cantor(puzzle, 9);
    if (ans[id] == -1) {
        puts("unsolvable");
        return 0;
    }

    int pos = ans[id];
    // cout << Q[pos].step;
    while (pos != -1) {
        cout << Q[pos].op;
        pos = Q[pos].fa;
    }

    return 0;
}

poj1077 Eight

原文：https://www.cnblogs.com/zbhfz/p/14318275.html