SOJ 1150 1151 1515 魔板

我和算法的日常相爱相杀。

康托展开

康托展开是一个全排列到一个自然数双射,常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。

这个上学期在讲哈希的时候老师提及过,在这里可以认为是一个全排列的压缩算法。

问题描述

魔板由 8 个大小相同方块组成,分别用涂上不同颜色,用 1 到 8 的数字表示。

其初始状态是

1 2 3 4

5 6 7 8

对魔板可进行三种基本操作:

A 操作(左右两列互换):

3 4 1 2

7 8 5 6

B 操作(每次以行循环左移一个):

2 3 4 1

6 7 8 5

C 操作(中间四小块逆时针转一格):

1 3 7 4

5 2 6 8

用上述三种基本操作,可将任一种状态转换成另一种状态。

问题求解

Input

输入包括多个要求解的魔板,每个魔板用三行描述。

第一行步数 N(N<=100),表示最多容许的步数。

第二、第三行表示目标状态,按照魔板的形状,颜色用 1 到 8 的表示。

当 N 等于 - 1 的时候,表示输入结束。

Output

对于每一个要求解的魔板,输出一行。

首先是一个整数 M,表示你找到解答所需要的步数。接着若干个空格之后,从第一步开始按顺序给出 M 步操作(每一步是 A、B 或 C),相邻两个操作之间没有任何空格。

注意:如果不能达到,则 M 输出 -1 即可。

http://sicily.tech/1515

思路

BFS + 去重

去重可以用 std::set,记录比较的时候为了压缩内存可以用康托展开。

#include "iostream"
#include "set"
#include "queue"
#include "string"
using namespace std;

class MagicBoard
{int factorial(int n)
    {if (n == 1 || n == 0) return 1;
        else return n * factorial(n-1);
    }

public:
    int step;
    int magicBoard[8];
    string op;

    MagicBoard() : step(0)
    {for (int i = 0; i < 8; ++i)
            magicBoard[i] = i+1;
    }

    MagicBoard(int cantorExpansion) : step(0)
    {int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
        vector<int> v(arr, arr+8);
        for (int i = 0; i < 8; ++i)
        {int index = cantorExpansion / factorial(7-i);
            magicBoard[i] = v[index];
            v.erase(v.begin() + index);
            cantorExpansion %= factorial(7-i);
        }
    }

    int getCantorExpansion()
    {
        int result = 0;
        for (int i = 0; i < 8; ++i)
        {
            int cnt = 0;
            for (int j = i+1; j < 8; ++j)
                if (magicBoard[j] <magicBoard[i]) cnt++;
            result += cnt * factorial(7-i);
        }
        return result;
    }

    MagicBoard operationA()
    {swap(magicBoard[0], magicBoard[2]);
        swap(magicBoard[1], magicBoard[3]);
        swap(magicBoard[4], magicBoard[6]);
        swap(magicBoard[5], magicBoard[7]);
        op += 'A';
        step++;
        return *this;
    }

    MagicBoard operationB()
    {int tmp = magicBoard[0];
        magicBoard[0] = magicBoard[1];
        magicBoard[1] = magicBoard[2];
        magicBoard[2] = magicBoard[3];
        magicBoard[3] = tmp;
        tmp = magicBoard[4];
        magicBoard[4] = magicBoard[5];
        magicBoard[5] = magicBoard[6];
        magicBoard[6] = magicBoard[7];
        magicBoard[7] = tmp;
        op += 'B';
        step++;
        return *this;
    }

    MagicBoard operationC()
    {int tmp = magicBoard[1];
        magicBoard[1] = magicBoard[2];
        magicBoard[2] = magicBoard[6];
        magicBoard[6] = magicBoard[5];
        magicBoard[5] = tmp;
        op += 'C';
        step++;
        return *this;
    }
};

int main(int argc, char const *argv[])
{
    int N;
    while (cin>> N && N != -1)
    {queue<MagicBoard> q;
        set<int> s;
        MagicBoard init, tmp, res;
        for (int i = 0; i < 8; ++i)
            cin >> tmp.magicBoard[i];
        int des = tmp.getCantorExpansion();
        q.push(init);
        s.insert(init.getCantorExpansion());
        bool nf = true;
        while (!q.empty())
        {if (q.front().getCantorExpansion() == des)
            {
                nf = false;
                res = q.front();
                break;
            }
            else
            {MagicBoard ele = MagicBoard(q.front()).operationA();
                if (s.find(ele.getCantorExpansion()) == s.end() && ele.step <= N)
                {if (ele.getCantorExpansion() == des)
                    {
                        nf = false;
                        res = ele;
                        break;
                    }
                    else
                    {q.push(ele);
                        s.insert(ele.getCantorExpansion());
                    }
                }
                ele = MagicBoard(q.front()).operationB();
                if (s.find(ele.getCantorExpansion()) == s.end() && ele.step <= N)
                {if (ele.getCantorExpansion() == des)
                    {
                        nf = false;
                        res = ele;
                        break;
                    }
                    else
                    {q.push(ele);
                        s.insert(ele.getCantorExpansion());
                    }
                }
                ele = MagicBoard(q.front()).operationC();
                if (s.find(ele.getCantorExpansion()) == s.end() && ele.step <= N)
                {if (ele.getCantorExpansion() == des)
                    {
                        nf = false;
                        res = ele;
                        break;
                    }
                    else
                    {q.push(ele);
                        s.insert(ele.getCantorExpansion());
                    }
                }
                q.pop();}
        }
        if (nf) cout << -1 << endl;
        else cout <<res.step <<' '<< res.op << endl;}
    return 0;
}