SOJ 1151 魔板

题目描述
SOJ 1151是一道关于搜索的题目，魔板由八个方块组成，为一个2×4的矩阵，每块分别用1-8表示颜色区别，每一次均可以对其进行一次操作，其中可选操作为A，B，C：
A操作（上下行互换）
B操作（每次以行循环右移一个）
C操作（中间四小块顺时针转一格）
魔板初始状态为

1 2 3 4

8 7 6 5

给定一个目标状态，给定一个最大步数，要求求出从初态到目标态的最小操作序列，若超出最大步数则停止计算，输出-1

算法思想及解题用到的主要数据结构
由于本题的目标是尽快找到解，通过分析，我们可以知道从一个状态执行三种操作到达其下一个状态，在决策树中三个分支是代价一致的（即所有深度相同的节点代价相同），因此我们可以通过广度优先搜索搜寻解，其找到的解必定是最优解。
广度优先搜索的过程我们需要用到队列这种数据结构来辅助。
关于魔板的表示方式，我们可以使用字符串，定义一个结构体board,其中包括两个字符串status和op，status为一个表示此魔板状态的8长字符串，只有字符1-8，op表示初态转换为当前魔板状态的操作序列，由字符ABC组成，初态的op为空字符串。
同时，由于由1-8组成的8串只有8！=40320种不同情况，我们可以想办法记录已经搜索过的状况，确保没有重复搜索。
记录已经搜索状况的数据结构，需要用到关联数组。

详细解题思路
根据广搜的原理，我们首先将目标状态放入队列，对于维护队列的队头，我们先检查其符不符合目标状态，若不符合，我们获得它经过三种操作后的三种状态，放入队尾，然后把当前队头弹出队列。直到我们找到目标状态，或者操作的深度已经超过最大限度，循环结束。
同时为了方便判断重复状态，我们在将状态放入队列之前还需要将其记录下来，以map为例，我们在将下一状态放入队列前，先在map中搜索，判断其是否为已经搜索过的状态，若否，我们将该状态的<status, op>数据对放入用于判断的map中。

逐步求精算法描述
由于在map中搜索也需要一定的时间复杂度，为了避免不必要的搜索，我们可以在插入队列前先做一定的剪枝。
考虑如同XX……XX的一个操作序列/字符串，我们可以知道，一个状态连续进行两次A操作会变为它本身，一个不必搜索的状态，在计算三种操作能到达的状态前，我们可以先分析当前状态的op串的最后一个字符串，若为A，则我们不必搜寻其进行A操作后得到的下一个状态，达到剪枝的目的，并节省需要在map中搜索才得出结果的时间。
同理XX……X = XX……XBBBB，XX……X = XX……XCCCC，可以帮助剪枝。
当然，上面这个方法只是小儿科，当我们能将进行一次操作的复杂度降低时，便不需要上面的这个预分析的办法，下面讲讲两种优化技巧。

康托展开
康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。比如说题目中的这种情况，一个魔板状态相当于一个1到8的全排列状态，通过康托展开，我们可以用一个0 到 40319的数字表示8！种状态，又因为这是一个双射，很容易可以通过这个数字还原这个全排列。

位运算处理
模板状态的保存问题，我们看到题目，很自然会想到用一个2x4的字符矩阵来保存这个状态，又或者是一个大小为8的数组，所以储存一个状态占用8个字节。对于ABC三类操作，通过交换数组/矩阵内的元素位置实现。这里引入位运算的办法来简化这一过程。
8个1-8的十进制数，用二进制表示，每个数至少要4位，一共需要32位（四字节），即一个int类型的大小。我们就用一个int类型内的二进制位表示一个魔板状态。
这样一来，对数组内的元素交换位置，可以改为速度更快的微操作：
A(x) = (x ≪ 16) | (x ≫ 16)
前16位表示第一行，后16位表示第二行，将x左移16位和右移16位的结果合并，则实现上下行的交换
B(x) = [(x &0xFFF0FFF0) ≫ 4] | [(x &0x000F000F) ≪ 12]
(x &0x000F000F)，取出魔板的最右一列，左移12位变为左数第一列，将其余的三列（(x &0xFFF0FFF0)）右移4位，表示循环右移的结果
C(x) = (x &0xF00FF00F) | [(x &0x0F000000) ≫ 4] | [(x &0x00F00000) ≫ 16]
| [(x &0x00000F00) ≪ 16] | [(x &0x000000F0) ≪ 4]
相当于初始状态中2-3-6-7循环交换位置。
这一做法是一个同学的启发，他用位操作用得非常巧妙，经常受他启发。当然很多时候很多问题用位操作都可以加速，只是思考编码的过程如果不熟练的话需要更多的时间。

总结
N为状态总数,在预处理时,广度优先需要访问每个状态,对于每个状态需要O(log N)的时间复杂度。将其插入到关联数组中。在回答输入的查询时,对于每个查询需要O(log N)的时间复杂度来得到关联数组中的元素。假设一共有M个查询,则该算法的时间复杂度为O(Nlog N + Mlog N) = O((N + M) log N)。

简单地说，我们求精的思路过程是：
简单的广搜，没有记忆化（会有很多重复状态）->加入记忆化，记录已经走过的状态（判断一个状态有没有走过也需要时间）->剪枝，通过查看操作序列判断是否应该执行某操作，因若进行该操作，得到的状态必然为已经走过的（判断这个也需要时间）->把所有可能先搜出来并记录，对于每条查询，直接在答案中找。