【百题千解】题解 P2730 【魔板 Magic Squares】

Anye
Anye
发布于 2019-11-01 / 3 阅读
0
0

【百题千解】题解 P2730 【魔板 Magic Squares】

思路分析

这道题是一道非常典型的 BFS 题目, BFS 所面临的最大问题是判断重复。显然,如果每次判断重复都扫描一次队列,搜索的效率会非常低,会提高一个指数级,所以一般宽度搜索的判断重复都是运用数组来实现的。那么数组下标就需要用一个 Hash 函数来计算。因此,设计 Hash 函数就显得非常重要。

本题 Hash 函数的设计:我们很容易想到将 8 个数字按顺时针顺序组合成 8 进制(每个数字都减 1 )的 8 位基数。但是,这里最大的八进制数 76543210 ,转换成十进制数就是 16434824 ,也就是说要开大小为 16434824 的数组,如果题目强制空间限制,那么,数组下标会越界。

这里我们引入康托展开,即将一个排列对应成它在全排列中的序数,这样就不会 MLE 了。

如 { 1,2,3,4,···,n } 表示 1,2,3,4,···,n的一个排列,如 {1,2,3} 按从小到大排序,一共有6个: 1 2 3,1 3 2,2 1 3,2 3 1,3 1 2,3 2 1,分别代表数字 1,2,3,4,5,6,也就是把 10 进制数与一个排列对应起来。它们之间的对应关系可有康托展开来找到。如果想知道 321 时 {1,2,3}中第几大的数,可以这样考虑:第一位是 3 ,当第一位的数字小于 3 时,对应的排列数都小于 321,如 123,213.则小于 3 的数有 1,2,所以有 2×2! 个;再看小于第二位的数 2 ,小于 2 的数只有一个就是 1 ,所以有 1×1!=1。因此小于 321 的 {1,2,3} 排列数共有 2×2!+1×1!=5个,所以 321 是第六大的数。

再如 1324 是 {1,2,3,4} 排列数中第几大的数? 第一位数字是 1 ,小于 1 的数没有,是 0 个,即 0×3!;第二位数字是 3 ,小于 3 的数有 1,2,但 1 已经在第一位上,所以只有一个数 2 ,即 1×2!;第三位数字是 2 ,小于 2 的数字是 1 ,但是 1 在第一位上,所以有 0 个数,即 0×1!。因此比 1234小的排列有 0×3!+1×2!+0×1!=2个,所以 1324是第三大的数。

设 step[]记步数;记 i 的父节点为 prt[i];a[i]表示第 i 个序列采用哪种变换。


附上详细代码及解释

#include <bits/stdc++.h>
using namespace std;
int jc[10] = { 1, 1, 2, 6, 24, 120, 720, 5040 };//jc[i]=i!
int g, st, prt[50005], b[1000000] = { 0 }, step[50005];
char a[50005];
struct mb { int a[2][4]; } start, goal, q[90000];

int Turn(mb x)//康托展开
{
    int i, j, res = 0, t[8], s;

    for (i = 0; i < 4; i++) t[i] = x.a[0][i]; //构成序列
    for (i = 3; i >= 0; i--) t[7 - i] = x.a[1][i];
    for (i = 0; i < 8; i++) {
        s = 0;
        for (j = i + 1; j <= 7; j++) if (t[j] < t[i]) s++; //找到后面小于t[i]的值
        res += jc[7 - i] * s;
    }
    return res;
}

mb Change(int way, int num)//三种基本操作
{
    mb temp;

    if (way == 1) {//A
        for (int i = 0; i < 4; i++) temp.a[0][i] = q[num].a[1][i];
        for (int i = 0; i < 4; i++) temp.a[1][i] = q[num].a[0][i];
        return temp;
    }
    if (way == 2) {//B
        temp.a[0][0] = q[num].a[0][3];
        temp.a[1][0] = q[num].a[1][3];
        for (int i = 1; i < 4; i++) temp.a[0][i] = q[num].a[0][i - 1];
        for (int i = 1; i < 4; i++) temp.a[1][i] = q[num].a[1][i - 1];
        return temp;
    }
    if (way == 3) {//C
        temp.a[0][0] = q[num].a[0][0]; temp.a[0][3] = q[num].a[0][3];
        temp.a[1][0] = q[num].a[1][0]; temp.a[1][3] = q[num].a[1][3];
        temp.a[0][1] = q[num].a[1][1]; temp.a[0][2] = q[num].a[0][1];
        temp.a[1][2] = q[num].a[0][2]; temp.a[1][1] = q[num].a[1][2];
        return temp;
    }
}

void Print(int num)//递归输出结果
{
    if (num == 1) return;
    Print(prt[num]);
    cout << a[num];
}

void Bfs()
{
    int op = 1, cl = 1, i, t;
    mb temp;

    q[1] = start;
    step[1] = 0; prt[1] = 1;
    while (op <= cl) {
        for (i = 1; i <= 3; i++) {      //三种变换
            temp = Change(i, op);
            t = Turn(temp);         //计算对应序号
            if (!b[t]) {
                q[++cl] = temp;
                step[cl] = step[op] + 1;
                b[t] = 1;                       //标记
                prt[cl] = op;                   //prt[cl]:记录cl的父节点为prt[cl]
                a[cl] = char('A' + i - 1);      //a[cl]:表示第cl个序列采用哪种变换
                if (t == g) {
                    cout << step[cl] << endl; Print(cl); return;
                }
            }
        }
        op++;
    }
}
signed main()
{
    int i;

    for (i = 0; i < 4; i++) start.a[0][i] = i + 1;  //初始化起始状态
    for (i = 3; i >= 0; i--) start.a[1][i] = 8 - i;
    st = Turn(start); b[st] = 1;                    //标记起始状态
    for (i = 0; i < 4; i++) cin >> goal.a[0][i];    //读入目标状态
    for (i = 3; i >= 0; i--) cin >> goal.a[1][i];
    g = Turn(goal);                                 //计算目标状态的值
    if (g == st) {
        cout << 0; return 0;
    }                     //注意:起始状态和目标状态相同
    Bfs();
    return 0;
}


评论