学步园

八数码问题，这里的题意是将序列变为1,2,3,4,5,6,7,8，x的步骤，表示出x的变动，因为进行移动一定是x与某数的互换，所有总体上可以由x的移动来表示

u，d，l，r分别表示上下左右

利用哈希的方式构造结点查找表并且用以检查重复

#include"iostream"
#include"cstring"
#define EPT(m,n) for(int (m)=0;(m)<(n);(m)++)
using namespace std;

const int MAXSIZE = 567890;
const int ESIZE = 9;

typedef char State[ESIZE];

State q[MAXSIZE];
State t = {'1','2','3','4','5','6','7','8','x'};

int head[MAXSIZE];
int next[MAXSIZE];
int proc[MAXSIZE];
int last_step[MAXSIZE];
int add_zero[MAXSIZE];

char move[4] = {'r','l','d','u'};

int d[4][2] ={{0,1},{0,-1},{1,0},{-1,0}};

void init_lookup_table(){
	memset(head,0,sizeof(head));
}

int hash(State s){
	int v = 0;
	EPT(i,9){
		v = v * 10 + (s[i] - '0');
	}
	return v % MAXSIZE;
}

int try_to_insert(int s){
	int h = hash(q[s]);
	int u = head[h];    
	while(u){
		if(memcmp(q[u],q[s],sizeof(q[s])) == 0)
			return 0;
		u = next[u];            //下一个结点
	}
	next[s] = head[h];            //查找表头
	head[h] = s;
	return 1;
}

void print(int idx){
	if(last_step[idx] != 0)
		print(last_step[idx]);
	printf("%c",move[proc[idx]]);
}

int bfs(){
	init_lookup_table();
	int front = 0,rear = 1;
	int zero;
	EPT(e,9)
		if(q[0][e] == 'x'){
			zero = e;
			break;
		}
		add_zero[0] = zero;
		while(front < rear){
			State &u = q[front];
			if(memcmp(u,t,sizeof(t)) == 0){
				print(front);
				return 0;
			}
            zero = add_zero[front];
			EPT(i,4){
				int x = (zero % 3) + d[i][1];
				int y = (zero / 3) + d[i][0];
				if(x > -1 && x < 3 && y > -1 && y < 3){       //判断移动是否合法
					int tem = y * 3 + x;
					State &v = q[rear];
					memcpy(v,u,sizeof(u));
					v[tem] = v[tem] ^ v[zero];
					v[zero] = v[tem] ^ v[zero];
					v[tem] = v[tem] ^ v[zero];
					if(try_to_insert(rear)){
						proc[rear] = i;
						add_zero[rear] = tem;
						last_step[rear] = front;
						rear ++;
					}
				}
			}
			front ++;
		}
		return 1;
}

int main(void){
	EPT(i,9)
	{
		scanf("%c",q[0] + i);
		getchar();
	}
	if(bfs()){
		printf("unsolvable");
	}
	return 0;
}