SSL1092魔闆

算法

這題很明顯用搜尋做，但是用深搜的話容易逾時甚至出現死循環，不可取。我們就隻能用廣搜來做了。但廣搜的不足也顯而易見，沒有好的辦法能夠判斷新狀态是否與舊狀态重合。用普通隊列是完全不可能的，于是我想到了哈希表。是以這題的算法就确定下來，使用廣搜+哈希。

思路

既然是搜尋，就要有搜尋方向。題中給出ABC三種操作，那我們應該如何實作呢？用一個[3][8]的二維數組就可以解決。{{8,7,6,5,4,3,2,1},{4,1,2,3,6,7,8,5},{1,7,2,4,5,3,6,8}},分别代表A,B,C三種運算。

　　接下來是哈希函數的設計。這個很簡單，直接用除餘法。主要是除數的選擇。肯定要使用質數，有一種質數特别好記，31,331,3331,33331……都是質數，除了333333333331外。這道題就取333331作為除數。

代碼實作

送上AC代碼~~

#include<iostream>
#include<cstdio>
#define p 333331
#define maxx 1000000
using namespace std;
string h[maxx],s,state[maxx];
int f[maxx],num[maxx],tail,head; 
int rule[3][8]={{8,7,6,5,4,3,2,1},{4,1,2,3,6,7,8,5},{1,7,2,4,5,3,6,8}};
char ls[maxx];
bool hash(string s){
	int ans=0;
	for(int i=0;i<8;i++){
		ans=ans*10+s[i]-'0';
	}
	int i=0;ans%=p;
	while(i<maxx && h[(i+ans)%p]!="" && h[(i+ans)%p]!=s){
		i++;
	}
	if(h[(i+ans)%p]==""){
		h[(i+ans)%p]=s;
		return false;
	}
	else{
		return true;
	}
}
void bfs(){
	hash("12345678");
	state[1]="12345678";
	head=0;tail=1;
	do{
		head++;
		for(int i=0;i<3;i++){
			tail++; 
			f[tail]=head; 
			state[tail]=""; 
			num[tail]=num[head]+1; 
			if (i==0) ls[tail]='A'; else
			if (i==1) ls[tail]='B'; else
			if (i==2) ls[tail]='C'; 
			for(int j=0;j<8;j++){
				state[tail]+=state[head][rule[i][j]-1];
			}	
			if(hash(state[tail])) tail--;
			else if(state[tail]==s) return;
			
		}
	}while(head<tail);
}
void print(int x){
	if(x==1){
		return;
	}
	print(f[x]);
	printf("%c",ls[x]);
}
int main(){
	int xx;
	for (int i=0;i<8;i++)
	 {scanf("%d",&xx);s+=xx+48; }
	if (s=="12345678"){
		printf("0");
		return 0;
	}
	bfs(); 
	printf("%d\n",num[tail]); 
	print(tail);
	return 0;
}