首页 > ACM题库 > HDU-杭电 > HDU 3287-Theta Puzzle[解题报告]HOJ
2014
03-13

HDU 3287-Theta Puzzle[解题报告]HOJ

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.
Interior Points of Lattice Polygons

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.
Interior Points of Lattice Polygons

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
3 ADCEFB
4 ADCEBF
5 FEDCBA
6 FEDCAB
7 ECBFAD
8 ECBFDA
9 DCEBFA
10 DCEBAF
11 CBEADF
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));因为第二种解法如果数组有重复元素 就不正确