[UVA][雙向BFS] 704 - Colour Hash
Colour Hash
| Colour Hash |
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.
Input
Input for your program consists of several puzzles. The first line of the input will contain an integer n specifying the number of puzzles. There will then be n lines each containing 24 integers separated with one white space, describing the initial puzzle configuration as explained above.
Output
For each configuration your program should output one line with just one number representing the solution. Each movement is encoded using one digit from 1 to 4 in the following way:
| 1 | Left Wheel Clockwise rotation |
| 2 | Right Wheel Clockwise rotation |
| 3 | Left Wheel Counter-Clockwise rotation |
| 4 | Right Wheel Counter-Clockwise rotation |
No space should be printed between each digit. Since multiple solutions could be found, you
should print the solution that is encoded as the smallest number. The
solution will never require more than 16 movements.
If no solution is found you should print ``NO SOLUTION WAS FOUND IN 16 STEPS". If you are given the final position you should print ``PUZZLE ALREADY SOLVED".
Sample Input
3 0 3 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1 0 3 4 5 0 3 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1 0 9 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 3 0 1 2 1
Sample Output
PUZZLE ALREADY SOLVED 1434332334332323 NO SOLUTION WAS FOUND IN 16 STEPS
Miguel A. Revilla
2000-02-09
題目描述：
那個有點複雜的轉盤遊戲, 要求從起始狀態轉到目標狀態, 操作有四種左邊順時針, 右邊順時針, 左邊逆時針, 右邊逆時針, 但只求 16 步以內(含)的解。輸出的時候字典順序越小越好, 操作次數越少越好。
題目解法：
操作 4 種, 最多 16 步, 因此最慘會到 4^16 = 2^32 基本上不會在時限內通過,
因此考慮剖半, 先從目標狀態使用 bfs 找到 8 步內的最佳解, 最多 2^16 = 65536 個狀態,
然後對每組起始狀態也使用 bfs 找到 8 步內的解, 看能不能撞到預處理的解。
因此每組操作只需要 O(65536), 降了非常多。
同時也是雙向 bfs 的 O(sqrt(n)) 的思路。
#include <stdio.h>
#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
map<string, string> R;
string left1(string v) {
static char t1, t2;
string tn;
tn = v;
t1 = tn[11], t2 = tn[10];
tn[11] = tn[9], tn[10] = tn[8], tn[9] = tn[7];
tn[8] = tn[6], tn[7] = tn[5], tn[6] = tn[4];
tn[5] = tn[3], tn[4] = tn[2], tn[3] = tn[1];
tn[2] = tn[0], tn[1] = t1, tn[0] = t2;
return tn;
}
string right2(string v) {
static char t1, t2;
string tn;
tn = v;
t1 = tn[9], t2 = tn[10];
tn[9] = tn[11], tn[10] = tn[12], tn[11] = tn[13];
tn[12] = tn[14], tn[13] = tn[15], tn[14] = tn[16];
tn[15] = tn[17], tn[16] = tn[18], tn[17] = tn[19];
tn[18] = tn[20], tn[19] = t1, tn[20] = t2;
return tn;
}
string left3(string v) {
static char t1, t2;
string tn;
tn = v;
t1 = tn[9], t2 = tn[10];
tn[9] = tn[11], tn[10] = tn[0], tn[11] = tn[1];
tn[0] = tn[2], tn[1] = tn[3], tn[2] = tn[4];
tn[3] = tn[5], tn[4] = tn[6], tn[5] = tn[7];
tn[6] = tn[8], tn[7] = t1, tn[8] = t2;
return tn;
}
string right4(string v) {
static char t1, t2;
string tn;
tn = v;
t1 = tn[11], t2 = tn[10];
tn[11] = tn[9], tn[10] = tn[20], tn[9] = tn[19];
tn[20] = tn[18], tn[19] = tn[17], tn[18] = tn[16];
tn[17] = tn[15], tn[16] = tn[14], tn[15] = tn[13];
tn[14] = tn[12], tn[13] = t1, tn[12] = t2;
return tn;
}
void build() {//bfs
R["034305650121078709T90"] = "";
queue<string> Q;
string tn, next;
Q.push("034305650121078709T90");
while(!Q.empty()) {
tn = Q.front(), Q.pop();
string &step = R[tn];
if(step.length() >= 8)//stop extend
continue;
// 1 left wheel clockwise, build by inverse
next = left3(tn);
string &o1 = R[next];
if(o1 == "") o1 = "1" + step, Q.push(next);
// 2 right wheel clockwise
next = right4(tn);
string &o2 = R[next];
if(o2 == "") o2 = "2" + step, Q.push(next);
// 3 left wheel counter-clockwise
next = left1(tn);
string &o3 = R[next];
if(o3 == "") o3 = "3" + step, Q.push(next);
// 4 right wheel counter-clockwise
next = right2(tn);
string &o4 = R[next];
if(o4 == "") o4 = "4" + step, Q.push(next);
}
}
void sol(string tn) {
map<string, string> rR;
map<string, string>::iterator it;
string next;
queue<string> Q;
rR[tn] = "";
Q.push(tn);
while(!Q.empty()) {
tn = Q.front(), Q.pop();
string &step = rR[tn];
it = R.find(tn);
if(it != R.end()) {
cout << step << it->second << endl;
return;
}
if(step.length() >= 8)
continue;
next = left1(tn);
string &o1 = rR[next];
if(o1 == "") o1 = step+"1", Q.push(next);
// 2 right wheel clockwise
next = right2(tn);
string &o2 = rR[next];
if(o2 == "") o2 = step+"2", Q.push(next);
// 3 left wheel counter-clockwise
next = left3(tn);
string &o3 = rR[next];
if(o3 == "") o3 = step+"3", Q.push(next);
// 4 right wheel counter-clockwise
next = right4(tn);
string &o4 = rR[next];
if(o4 == "") o4 = step+"4", Q.push(next);
}
puts("NO SOLUTION WAS FOUND IN 16 STEPS");
}
int main() {
build();
int testcase;
scanf("%d", &testcase);
while(testcase--) {
int i, x;
string s = "";
for(i = 0; i < 24; i++) {
scanf("%d", &x);
if(i < 21) {
if(x == 10)
s += 'T';
else
s += (char)(x + '0');
}
}
if(s == "034305650121078709T90")
puts("PUZZLE ALREADY SOLVED");
else
sol(s);
}
return 0;
}
/*
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
*/