本文主要是介绍UVa 704 - Colour Hash, 双向bfs，很给力，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=110&page=show_problem&problem=645
类型：隐式图搜索，双向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:
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:
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 红色(骨头型)
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 1 0 3 4 3 0 5 6 5 0 1 0 7 8 7 0 9 10 9 0 5 0 1
/* 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");}elseprintf("NO SOLUTION WAS FOUND IN 16 STEPS\n");}} return 0;
}—— 生命的意义，在于赋予它意义。
这篇关于UVa 704 - Colour Hash, 双向bfs，很给力的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
