2014
03-13

# Theta Puzzle

The Theta Puzzle consists of a base with 6 positions at the vertices of a regular hexagon and another position at the center, connected as shown in the figure below. There are six tokens labeled A, B, C, D, E and F. A single move of the puzzle is to move a token to an adjacent empty position (along an allowed connection � the line segments in the diagram below). The idea of the puzzle is to start with an initial arrangement of tokens with the center empty and, by a sequence of moves, get to the configuration in the figure below.

An initial position for the puzzle is given by a permutation of the letters A through F. The first letter starts at A in the figure, the next at B and so on.
A sequence of moves is specified by listing the labels of tokens to be moved, in the order they are to be moved.
For example, to solve the puzzle FACDBE, use the moves BEFAB.

Note: Not all starting permutations can be solved.
Write a program which, given an initial permutation, either finds the shortest sequence of moves to solve the puzzle or determines that there is no solution.

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by a permutation of the letters A through F giving the initial puzzle position.

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by a permutation of the letters A through F giving the initial puzzle position.

12
1 FACDBE
2 ABCDEF
5 FEDCBA
6 FEDCAB
8 ECBFDA
9 DCEBFA
10 DCEBAF
12 BDEAFC

1 5 BEFAB
2 0
3 19 DABFECABFEDBACDEFAB
4 NO SOLUTION
5 29 BCDEBCAFBCAFBCEDFAECBAFDCBAFE
6 NO SOLUTION
7 19 CBFACBFACDEFACDEFAB
8 NO SOLUTION
9 13 CDAFBEDCBEDCB
10 NO SOLUTION
11 21 DAEBDAEBDCFEBDCABEFAB
12 16 FAEDBCAFBCAFEDCB

#include<iostream>
#include<cstring>
#include<cstdio>
#include <string>
#include <deque>
#include<cmath>
#include<algorithm>
using namespace std;

struct node{
int num;
int cnt;
string str;
}p[830000], tmp, t;

int p7[8] = {0, 1, 7, 49, 343, 2401, 16807, 117649};
int tnum[8];
int num = 1 * p7[1] + 2 * p7[2] + 3 * p7[3] + 4 * p7[4] + 5 * p7[5] + 6 * p7[6] ;

int tu[8][8] ={
0, 1, 2, 3, 4, 5, 6, 7,
0, 0, 1, 0, 0, 0, 6, 0,
0, 1, 0, 3, 0, 0, 0, 7,
0, 0, 2, 0, 4, 0, 0, 0,
0, 0, 0, 3, 0, 5, 0, 0,
0, 0, 0, 0, 4, 0, 6, 7,
0, 1, 0, 0, 0, 5, 0, 0,
0, 0, 2, 0, 0, 5, 0, 0,
};
deque<node> q;
int maxx = 0;
void init(){
p[num].num = num;
p[num].cnt = 0;
q.push_back(p[num]);
while(!q.empty()){
tmp = q.front(); q.pop_front();
int k;
for(int i = 1, n = tmp.num;i < 8; i ++){
tnum[i] = n % 7;
if(tnum[i] == 0) k = i;
n /= 7;
}

for(int j = 1; j < 8; j ++)
if(tu[k][j]){
t.cnt = tmp.cnt + 1;
t.num = tmp.num - p7[j] * tnum[j] + p7[k] * tnum[j];
if(p[t.num].num == 0) {
t.str = tmp.str + (char)(tnum[j] + 'A' - 1);
q.push_back(t);
p[t.num] = t;
}
}
}
}

int main(){
init();
string s;
int T, t;
scanf("%d", &T);
while(T --){
scanf("%d", &t);
cin>>s;
int num = 0;
for(int i = 0; i < s.length(); i ++){
num += p7[i + 1] * (s[i] - 'A'+ 1);
}
s = p[num].str;
string str(s.rbegin(), s.rend());
if(p[num].cnt == 0 && num != 114381) cout<<t<<" "<<"NO SOLUTION"<<endl;
else cout<<t<<" "<<p[num].cnt<<" "<<str<<endl;
}
}

1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确