usaco_3_2_5_msquare_bfs找出一种排列在全排列中的位置.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROB:msquare
LANG: C++
*/
/*
这道题是BFS+Hash
在做哈希时，以为8的全排列为40320，所以找到序列是全排列中第几个元素就可以。
介绍一下字符串的一种hash 函数，对这题非常有用。如果叙述不清，请参看05年集训队李羽修的论文。
对于一种排列方式（可视为是一个字符串），计算它在所有排列方式中排第ｘ位，这样就可以做到一一对应
。对其从右往左数的第i位进行如下操作：
计算i位置后比第i位小的字符个数p。
        x=x+(i-1)!*ｐ。
最后，x=x+1 。
X即计算出。
用一个布尔数组used来判重，用整形数组a[40500][2]来记录具体路径.
我这里a[i][0]记录的是hash值为i的魔板状态的前一步的hash值，a[i][1]记录从上一状态得到hash值为i的魔板状态的变化方法。
这样在输出时只需从后往前找，一直找到a[1][0]=0结束，然后逆序输出即可。
*/
#include <fstream>
#include <iostream>
#include <string>
#include <memory>
#include <algorithm>
#include <queue>
#include <stack>
#define cin fin
using namespace std;
ifstream fin("msquare.in");
ofstream fout("msquare.out");
int power(int a)
{
	int s=1;
	for(int i=a;i>0;i--)
		s*=i;
	return s;
}
int hashf(string s)
{
	int a=0,t;
	for(int i=0;i<7;i++){
		t=0;
		for(int j=i+1;j<8;j++) if(s[j]<s[i]) t++;
		a+=power(7-i)*t;
	}
	return ++a;
}
int main()
{
	int i,j,k,n;
	bool used[40500];
	int a[40500][2];
	char temp;
	string s,st,s1;
	queue<string> q;
	s.assign("12345678");
	memset(used,false,sizeof(used));
	st.assign(s);
	for(i=0;i<8;i++)
		cin>>st[i];
//  reverse(&st[4],st.end());
	q.push(s);
	used[1]=true;
	a[1][0]=0;a[1][1]=0; //0为之前数，1为决策
	while(!q.empty())
	{
		s.assign(q.front());
		q.pop();
		k=hashf(s);
		if(!s.compare(st)) break;
		s1.assign(s);													//A
		reverse(s1.begin(),s1.end());     
		j=hashf(s1);
		if(!used[j] && a[k][1]!=1){
			q.push(s1);
			used[j]=true;
			a[j][0]=k;
			a[j][1]=1;
		}
		s1[0]=s[3];s1[3]=s[2];s1[2]=s[1];s1[1]=s[0];					//B
		s1[7]=s[4];s1[4]=s[5];s1[5]=s[6];s1[6]=s[7];
		j=hashf(s1);
		if(!used[j]){
			q.push(s1);
			used[j]=true;
			a[j][0]=k;
			a[j][1]=2;
		}
		s1.assign(s);													//C
		s1[1]=s[6];s1[2]=s[1];s1[5]=s[2];s1[6]=s[5];
		j=hashf(s1);
		if(!used[j]){
			q.push(s1);
			used[j]=true;
			a[j][0]=k;
			a[j][1]=3;
		}
	}
	stack<char> S;
	while(k!=0){
		
		S.push(char(a[k][1]+64));
		k=a[k][0];
	}
	S.pop();
	fout<<S.size()<<endl;
	while(!S.empty()){
		temp=S.top();
		S.pop();
		fout<<temp;
	}
	fout<<endl;
	return 0;
}