UVa 704 - Colour Hash, 双向bfs，很给力

类型：隐式图搜索，双向bfs

原题：
This puzzle consists of two wheels. Both wheels can rotate both clock and counter-clockwise. They contain 21 coloured pieces, 10 of which are rounded 易做图s and 11 of which are separators. Figure 1 shows the final position of each one of the pieces. Note that to perform a one step rotation you must turn the wheel until you have advanced a 易做图 and a separator.

Figure 1. Final puzzle configuration
Your job is to write a program that reads the puzzle configuration and prints the minimum sequence of movements required to reach the final position. We will use the following integer values to encode each type of piece:

0 grey separator
1 yellow 易做图
2 yellow separator
3 cyan 易做图
4 cyan separator
5 violet 易做图
6 violet separator
7 green 易做图
8 green separator
9 red 易做图
10 red separator

A puzzle configuration will be described using 24 integers, the first 12 to describe the left wheel configuration and the last 12 for the right wheel. The first integer represents the bottom right separator of the left wheel and the next eleven integers describe the left wheel clockwise. The thirteenth integer represents the bottom left separator of right wheel and the next eleven integers describe the right wheel counter-clockwise.
The final position is therefore encoded like:
0 3 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1
If for instance we rotate the left wheel clockwise one position from the final configuration (as shown in Figure 2) the puzzle configuration would be encoded like:
2 1 0 3 4 3 0 5 6 5 0 1 0 7 8 7 0 9 10 9 0 5 0 1

Figure 2. The puzzle after rotating the left wheel on step clockwise from the final configuration.

题目大意：
有一种拼盘有两个轮子, 而这两个轮子都可以顺时针转和逆时针转. 拼盘有21 片, 10 片是有点圆的三角形, 而另外11 片则是骨头型. 图1 是所要拼成的目标. 记住一个"步骤"是你必须转动其中一个轮子往顺时针或逆时针的方向直到拼盘的每一片的边缘都能和他旁边的那几片的边缘重合在一起.
你的任务是写一个程式读入拼盘一开始的状态并且输出一个能够达成目标的最短转动序列,我们会用底下的数字来表示每一片:

0 灰色(骨头型)
1 黄色(三角形)
2 黄色(骨头型)
3 蓝色(三角形)
4 蓝色(骨头型)
5 紫色(三角形)
6 紫色(骨头型)
7 绿色(三角形)
8 绿色(骨头型)
9 红色(三角形)
10 红色(骨头型)

我们可以用24个整数来描述一个拼盘的状态,前12个数描述左边的轮子而后12个数描述右边的轮子
我们可以把最终的目标状态用以下这24个数字的序列的来表示:
0 3 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1
而如果我们把最终的盘面的左轮往顺时针方向转一格(如图2), 那它的状态序列就会变成这样:
2 1 0 3 4 3 0 5 6 5 0 1 0 7 8 7 0 9 10 9 0 5 0 1

分析与总结：

这题挺给力的。首先，根据题意可以看出有四种旋转可以改变状态，旋转之后序列就会根据旋转而改变。所以为了方便起见，专门写一个旋转函数来处理，旋转后，对于左右两个盘，改变的只有开始和结尾的几个数字，所以有大部分可以用memcpy整块复制而节约时间，对于改变的部分手动给它赋值。友情提示：写旋转函数时需要保持清醒的头脑，否则很容易转晕而写错。

本来我想说写完旋转函数，这题就算完成了一半，但是我错了。

由于我就没有注意到有16层状态所以很天真的直接单向bfs搜索，程序也很快很开心就写完了，但是问题随之而来，由于第二个测试样例
就需要16步，也就是说要搜到16层，需要的状态数量是十分巨大的！！所以在自己的电脑上一直出不来，运行错误。。。

一般出现这个情况大多是数组开小了，所以我一直不断地加大数组，结果还是无法出结果。

于是才注意到层数太多，状态也太多了，根本无法单向搜出来。。。

最终，借鉴了双向bfs的思想，先逆向从结果状态搜索8层，然后再从正向搜索，一旦正向搜索“碰到”了逆向搜索搜出来的状态，那么即得出答案。如果正向搜到第8层还没有“碰到”逆向搜到的状态，那么就表示无解。由于目标状态只有一个，所以逆向搜索只要搜一次就可以了。

然后就是正向搜索部分和逆向搜索部分的路径输出，分别写两个函数来输出。注意逆向搜索时保存的路径方向，应该是相反的。

对于判重，因为偷懒，直接用map来做了。。。

提交后一次AC，而且用map的速度还不错，这题的数据应该比较水。

[cpp]
/* UVa 704 - Colour Hash
* Time : 0.140s (UVA)
* 双向搜索 + map判重
*/

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<string>
#define MAXN 1000000
using namespace std;
map<string, int>vis;
map<string, int>back_vis;
typedef int State[24];
State goal = {0, 3, 4, 3, 0, 5, 6, 5, 0, 1, 2, 1, 0, 7, 8, 7, 0 ,9, 10,9 ,0, 1, 2, 1}, start;
State que[MAXN];
int step[MAXN], father[MAXN], path[MAXN], ans;
int back_father[MAXN], back_path[MAXN];

// 旋转函数
void rotate(int *next, int *origin, int dir){
    if(dir==1){ // 左盘顺时针转
        next[0] = origin[10], next[1] = origin[11];
        memcpy(next+2, origin, sizeof(int)*10); // 大块的，连续数组元素的用memcpy节约时间
        memcpy(next+12, origin+12, sizeof(int)*9);
        next[21]=origin[7], next[22] = origin[8], next[23] = origin[9];
    }
    else if(dir==2){ // 右盘顺时针转
        memcpy(next+12, origin+14, sizeof(int)*10);
        next[22] = origin[12], next[23] = origin[13];
        memcpy(next, origin, sizeof(int)*9);
        next[9] = next[21], next[10] = next[22], next[11] = next[23];
    }
    else if(dir==3){ // 左盘逆时针转
        memcpy(next, origin+2, sizeof(int)*10);
        next[10] = origin[0], next[11] = origin[1];
        memcpy(next+12, origin+12, sizeof(int)*9);
        next[21]=next[9], next[22]=next[10], next[23]=next[11];
    }
    else if(dir==4){ // 右盘逆时针转
        next[12] = origin[22], next[13] = origin[23];
        memcpy(next+14, origin+12, sizeof(int)*10);
        memcpy(next, origin, sizeof(int)*9);
        next[9] = next[21], next[10] = next[22], next[11] = next[23];
    }
}
// 把状态转换成字符串
inline string change_state(State &s){
    string str;
    for(int i=0; i<24; ++i)
        str += s[i]+'0';
    return str;
}

inline int try_to_insert(int s){

补充：软件开发 , C++ ,