類型：隱式圖搜索，雙向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 triangles 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 triangle 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 triangle
2 yellow separator
3 cyan triangle
4 cyan separator
5 violet triangle
6 violet separator
7 green triangle
8 green separator
9 red triangle
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){
string str = change_state(que[s]);
if(!vis[str]){
vis[str]=1;
return true;
}
return false;
}
inline int back_try_to_insert(int s){
string str = change_state(que[s]);
if(!back_vis[str]){
back_vis[str]=s; //保存在隊列在隊列中的位置，而不是1或者true,方便後面輸出路徑
return true;
}
return false;
}
bool back_bfs(){ //逆向搜索
memset(back_father, 0, sizeof(back_father));
step[0] = step[1] = 0;
back_vis.clear();
back_vis[change_state(goal)] = 1;
int front=0, rear=1;
memcpy(que[0], goal, sizeof(goal));
while(front < rear){
State &s = que[front];
if(step[front] > 8){ // 超過8步不再搜索
++front; continue;
}
for(int i=1; i<=4; ++i){
State &next = que[rear];
rotate(next, s, i);
step[rear] = step[front]+1;
if(back_try_to_insert(rear)){
back_father[rear] = front;
switch(i){ // 因為是逆向搜索，所以方向保存的也要是相反的
case 1:back_path[rear] = 3;break;
case 2:back_path[rear] = 4;break;
case 3:back_path[rear] = 1;break;
case 4:back_path[rear] = 2;break;
}
rear++;
}
}
++front;
}
return false;
}
bool bfs(){ // 正向搜索
memset(father, 0, sizeof(father));
step[0] = 0;
vis.clear();
vis[change_state(start)] = 1;
int front=0, rear=1;
memcpy(que[0], start, sizeof(start));
while(front < rear){
State &s = que[front];
if(step[front] > 8) {++front; continue;}
if(memcmp(s, goal, sizeof(goal))==0){
ans = front;
return false;
}
if(back_vis[change_state(s)]){
ans = front;
return true;
}
for(int i=1; i<=4; ++i){
State &next = que[rear];
rotate(next, s, i);
step[rear] = step[front]+1;
if(try_to_insert(rear)){
father[rear]=front; path[rear]=i;
rear++;
}
}
++front;
}
ans = -1;
}
void print_path(int cur){ // 打印出正向搜索部分
if(cur){
print_path(father[cur]);
printf("%d",path[cur]);
}
}
void print_back(){ // 打印出逆向搜索部分
string str = change_state(que[ans]);
int cur = back_vis[str];
while(cur){
printf("%d", back_path[cur]);
cur = back_father[cur];
}
}
int main(){
freopen("input.txt","r",stdin);
int T;
back_bfs(); // 逆向搜索只需要一次就夠了
scanf("%d", &T);
while(T--){
for(int i=0; i<24; ++i)
scanf("%d", &start[i]);
if(memcmp(start, goal, sizeof(goal))==0)
printf("PUZZLE ALREADY SOLVED\n");
else{
bfs();
if(ans!=-1){
print_path(ans);
print_back();
printf("\n");
}
else www.2cto.com
printf("NO SOLUTION WAS FOUND IN 16 STEPS\n");
}
}
return 0;
}
作者：shuangde800
