P2730 魔闆 Magic Squares

不看題解肯定不會系列。。。

這道題可以用Cantor展開解決。

Cantor展開可以求出一個數組是在全排列中的第幾個。

具體怎麼操作自己百度。

Cantor展開的公式是：\(a[1] * (n - 1)! + a[2] * (n - 2)! + ... + a[n] * 0!\)

這裡注意一下：\(0!=1\)。

其中\(a[i]\)表示第\(i\)個數在\([i, n]\)這個區間的第幾大（最小為\(0\)，最大為\(n - i\)）。

這樣求出來的數字取值範圍是在\([0, n! - 1]\)。你願意的話可以一起+1。

這樣的話，對于這個魔闆的狀态，就可以套用Cantor展開，用\(8!\)的空間就可以存下來，如果不用的話需要一億。

然後我們可以用Cantor展開的值當下标，就可以精确無誤地取出每一個狀态。

代碼：

#include<cstdio>
#include<vector>
const int aa[] = {0, 8, 7, 6, 5, 4, 3, 2, 1};
const int bb[] = {0, 4, 1, 2, 3, 6, 7, 8, 5};
const int cc[] = {0, 1, 7, 2, 4, 5, 3, 6, 8};
const int frac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
struct Nodes
{
    int fa;
    int a[9];
    int dist;
    char how;
    bool mark;
} s[50005];
int end[9], end_cantor;
int queue[50005], front, rear;
int cantor(int* a)
{
    int ans = 0;
    for(int i = 1; i <= 8; i++)
    {
        int s = 0;
        for(int j = i + 1; j <= 8; j++)
        {
            if(a[i] > a[j]) s++;
        }
        ans += s * frac[8 - i];
    }
    return ans + 1;
}
Nodes changeA(Nodes x)
{
    Nodes ans;
    for(int i = 1; i <= 8; i++) ans.a[i] = x.a[aa[i]];
    return ans;
}
Nodes changeB(Nodes x)
{
    Nodes ans;
    for(int i = 1; i <= 8; i++) ans.a[i] = x.a[bb[i]];
    return ans;
}
Nodes changeC(Nodes x)
{
    Nodes ans;
    for(int i = 1; i <= 8; i++) ans.a[i] = x.a[cc[i]];
    return ans;
}
int bfs()
{
    for(int i = 1; i <= 8; i++) s[1].a[i] = i;
    queue[rear++] = 1; s[1].mark = true;
    while(front < rear)
    {
        int x = queue[front++];
        if(x == end_cantor) return s[x].dist;
        Nodes A = changeA(s[x]); int A_cantor = cantor(A.a);
        Nodes B = changeB(s[x]); int B_cantor = cantor(B.a);
        Nodes C = changeC(s[x]); int C_cantor = cantor(C.a);
        if(!s[A_cantor].mark)
        {
            s[A_cantor] = A;
            s[A_cantor].dist = s[x].dist + 1;
            s[A_cantor].fa = x;
            s[A_cantor].how = 'A';
            queue[rear++] = A_cantor; s[A_cantor].mark = true;
            
        }
        if(!s[B_cantor].mark)
        {
            s[B_cantor] = B;
            s[B_cantor].dist = s[x].dist + 1;
            s[B_cantor].fa = x;
            s[B_cantor].how = 'B';
            queue[rear++] = B_cantor; s[B_cantor].mark = true;
        }
        if(!s[C_cantor].mark)
        {
            s[C_cantor] = C;
            s[C_cantor].dist = s[x].dist + 1;
            s[C_cantor].fa = x;
            s[C_cantor].how = 'C';
            queue[rear++] = C_cantor; s[C_cantor].mark = true;
        }
    }
}
int main()
{
    for(int i = 1; i <= 8; i++) scanf("%d", &end[i]);
    end_cantor = cantor(end);
    printf("%d\n", bfs());
    std::vector<char> v;
    for(int i = end_cantor; i != 1; i = s[i].fa) v.push_back(s[i].how);
    for(int i = v.size() - 1; i >= 0; i--) printf("%c", v[i]);
    printf("\n");
    return 0;
}                

轉載于:https://www.cnblogs.com/Garen-Wang/p/9350579.html