POJ1077 HDU1043 Eight 八数码 (A*+康托展开)

题目大意：给出八数码的起点状态，求出能够到达到终点状态的步数的序列（不一定是要最短的步数）

终点状态为：1 2 3

4 5 6

7 8 x

思路：这道题有很多方法可以做，在这里我用的是A*算法。在保存每一步的具体路径的时候我们可以用康托展开。首先把每一位赋予一个权值，个位的权值是0！，十位是1！，百位是2!，千位是3!........然后统计当前数位在他后面比他小的数字有多少个，然后乘上当前数位的权值，最后再把每个数位得到的值加起来就是康托展开了。

例如序列 1 2 3 4 5 6 7 8 0 的展开：1后面比它小的有0，2后面比他小的有0。。。。因此该序列的康托展开 =0*0!+1*1!+1*2!+1*3!+1*4!+1*5!+1*6!+1*7!+1*8!

又如 4312 的展开 0*0!+0*1!+2*2!+3*3!

此题还有一个比较坑的地方就是如何保存路径的问题，我们可以在结构体中开一个长整型变量，把它视作4进制的，0代表向上走，1代表向下。。。具体参考我的代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<string>
#include<cctype>
#define LL long long
#define MAXN 370000
using namespace std;
int bv[10] = {1,1,2,6,24,120,720,5040,40320,362880};
char st[10],nd[10] = {"123456780"};
int dd[4] = {-3,3,-1,1};
char iindex[4] = {'u','d','l','r'};
int abs(int x){return x>0?x:-x;}

struct node
{
	char s[10];//当前状态
	int step;//当前深度
	int diff;//估值函数
	int pos;//当前0的位置
	LL path;//保存路径
	node(){}
	node(char *a,int b,int c,int d,LL e)
	{
		strcpy(s,a);
		step = b;
		diff = c;
		pos = d;
		path = e;
	}
	bool operator < (const node &a) const
	{
		return step + diff > a.step + a.diff;
	}
};

int Cantor(char *a)//康托展开
{
	int res = 0;
	for(int i = 0; i < 9; i++)
	{
		int cnt = 0;
		for(int j = i + 1; j < 9; j++)
			if(a[i] > a[j]) cnt++;
		res += bv[8-i]*cnt;
	}
	return res;
}

int G(char *a)//A*算法估值函数
{
	int res = 0;
	for(int i = 0; i < 9; i++)
		if(a[i]!='0'&&a[i]!=i+'1')
			res += (abs(i - (a[i] - '1'))/3 + abs(i - (a[i] - '1'))%3);
	return res;
}

void getpath(LL p,int steps)//输出路径
{
	string str="";
	int res[100];
	memset(res,0,sizeof res);
	int res_cnt = 0;
	
	for(int i = 1; i <= steps; i++)
	{
		res[++res_cnt] = p%4;
		p/=4;
	}
	
	for(int i = res_cnt; i >= 1; i--)
		str+=iindex[res[i]];
	cout<<str<<endl;
}

bool vis[MAXN];
int _pos;
void astar()
{
	memset(vis,0,sizeof vis);
	priority_queue<node> myque;
	
	int _diff = G(st);
	vis[Cantor(st)] = 1;
	myque.push(node(st,0,_diff,_pos,0));
	
	while(!myque.empty())
	{
		node now = myque.top();
		myque.pop();
		
		char ss[10];
		strcpy(ss,now.s);
		int hash;
		
		if(strcmp(ss,nd) == 0)//找到终点
		{
			getpath(now.path,now.step);
			return;
		}
		
		for(int i = 0; i < 4; i++)
		{
			int tpos = now.pos + dd[i];
			
			if(tpos > 8||tpos < 0||(tpos%3 != now.pos%3&&tpos/3 != now.pos/3)) continue;
			
			swap(ss[tpos],ss[now.pos]);
			hash = Cantor(ss);
			
			if(!vis[hash])//剪枝，避免重复
			{
				int nowdiff = G(ss);
				vis[hash] = 1;
				myque.push(node(ss,now.step+1,nowdiff,tpos,now.path*4+(LL)i));//最后一个变量更新路径
			}
			swap(ss[tpos],ss[now.pos]);
		}
	}
	//printf("unsolvable\n");
}

bool check()//统计逆序对
{
	int cnt = 0;
	for(int i = 0; i < 9; i++)
		for(int j = i+1; j < 9; j++)
			if(st[i] > st[j] && st[j] != '0') cnt++;
	if((cnt%2) == 0) return 1;
	return 0;
}

int main()
{
	char x;
	while(scanf("%c",&x) != EOF)
	{
		memset(st,0,sizeof st);
		int cnt=0;
		if(isdigit(x)) st[cnt++]=x;
		else if(x=='x') st[cnt++]='0',_pos=cnt-1;
		while(scanf("%c",&x)&&x!='\n')
		{
			if(isdigit(x)) st[cnt++]=x;
			else if(x=='x') st[cnt++]='0',_pos=cnt-1;
		}
		if(!check())//判断逆序对，剪枝
		{
			printf("unsolvable\n");
			continue;
		}
		astar();
	}
}