康托展开
康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。
这个上学期在讲哈希的时候老师提及过，在这里可以认为是一个全排列的压缩算法。
问题描述
魔板由 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 即可。
思路
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;
}
