蓝桥杯 历届试题 九宫重排 经典八数码问题 A*算法+康托展开

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring> 
#define MAX 400000
using namespace std ;

int visited[MAX];
int HASH[9]={1,1,2,6,24,120,720,5040,40320} ;
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}} ;
int des[3][3];

struct Node{
	int map[3][3] ;
	int x , y ;
	int hash ;
	int g , h , f;
	bool operator<(const Node &n1)const
	{
		//return h==n1.h ? (g>n1.g):(h>n1.h) ;
		return f!=n1.f?f>n1.f:h>n1.h ;
	}
	bool check()
	{
		if(x<0||y<0 || x>=3||y>=3)
		{
			return false ;
		}
		return true ;
	}
	//求哈希码用到了康托展开 
	void getHash()
	{
		int oth[9] , k = 0 ;
		for(int i = 0 ; i < 3 ; ++i)
		{
			for(int j = 0 ; j < 3 ; ++j)
			{
				oth[k++] = map[i][j] ;
			}
		}
		hash = 0 ; 
		for(int i = 0 ; i < 9 ; ++i)
		{
			int k = 0 ; 
			for(int j = 0 ; j < i ; ++j)
			{
				if(oth[i]<oth[j])
				{
					k++;
				}
			}
			hash += k*HASH[i] ;
		}
	}
	//求两点之间曼哈顿距离 
	void getH()
	{
		int oth[9] , k = 0 ;
		h = 0 ;
		for(int i = 0 ; i < 3 ; ++i)
		{
			for(int j = 0 ; j < 3 ; ++j)
			{
				int m = 0 , n = 0;
				for(m = 0 ; m < 3 ; ++m)
				{
					for(n = 0 ; n < 3 ; ++n)
					{
						if(map[i][j] == des[m][n])
						{
							goto  loop ;
						}
					}
				}
				loop:
				h += abs(m-i)+abs(n-j) ;
			}
		}
	}
}end;

//根据八数码的性质，，判断有无解 
bool judge(Node start , Node end)
{
	int s[9] , st = 0 , et = 0 ,k = 0;
	for(int i = 0 ; i < 3 ; ++i)
	{
		for(int j = 0 ; j < 3 ; ++j)
		{
			s[k++] =start.map[i][j] ;
		}
	}
	for(int i = 0 ; i < 9 ; ++i)
	{
		for(int j = 0 ; j < i ; ++j)
		{
			if(s[i]&&s[j]&&s[i]<s[j])
			{
				st++;
			}
		}
	}
	k = 0 ;
	for(int i = 0 ; i < 3 ; ++i)
	{
		for(int j = 0 ; j < 3 ; ++j)
		{
			s[k++] = end.map[i][j] ;
		}
	}
	for(int i = 0 ; i < 9 ; ++i)
	{
		for(int j = 0 ; j < i ; ++j)
		{
			if(s[i]&&s[j]&&s[i]<s[j])
			{
				et++;
			}
		}
	}
	return !((st&1)^(et&1)) ;
}

int AStar(Node start)
{
	priority_queue<Node> que;
	que.push(start);
	while(!que.empty())
	{
		Node now = que.top();
		que.pop() ;
		if(now.hash == end.hash)
		{
			return visited[now.hash] ;
		}
		for(int i = 0 ; i < 4 ; ++i)
		{
			Node next=now ;
			next.x += dir[i][0];
			next.y += dir[i][1];
			if(!next.check())	//坐标越界 
			{
				continue ;
			} 
			swap(next.map[now.x][now.y],next.map[next.x][next.y]) ;
			next.getHash() ;
			if(visited[next.hash] == 0)	//这个图未访问过 
			{
				next.getH();
				next.g++ ;
				next.f = next.g+next.h;
				visited[next.hash] = next.g ;
				que.push(next) ;
			}
			else
			{
				if(next.g+1<visited[next.hash])   //如果这个图访问过，，但是现在访问代价更小，，则更新对该图的访问代价 
				{
					next.getH();
					next.g++ ;
					next.f = next.g+next.h;
					visited[next.hash] = next.g ;
					que.push(next) ;
				}
			}
		}
	}
	return -1 ;
}
int main()
{
	char line[15];
	while(gets(line))
	{
		Node start;
		memset(visited,0,sizeof(visited)) ;
		for(int i = 0 ; i < 9 ; ++i)
		{
			if(line[i] != '.')
				start.map[i/3][i%3] = line[i]-'0' ;
			else
			{
				start.map[i/3][i%3] = 0 ;
				start.x = i/3 , start.y = i%3 ;
			}
		}
		gets(line);
		for(int i = 0 ; i < 9 ; ++i)
		{
			if(line[i] != '.')
				end.map[i/3][i%3] = line[i]-'0' ;
			else
				end.map[i/3][i%3] = 0 ;
			if(line[i] != '.')
				des[i/3][i%3] = line[i]-'0' ;
			else
				des[i/3][i%3] = 0 ;
		}
		end.getHash() ;
		end.g = -1;
		end.getH();
		end.f = end.g+end.h ;
		start.getHash() ;
		start.getH() ;
		start.g = 0 ;
		start.f = start.g+start.h ;
		visited[start.hash] == 1; 
		if(!judge(start,end))
		{
			printf("-1\n") ;
			continue ;
		}
		if(start.hash == end.hash)
		{
			printf("0\n") ;
			continue ;
		}
		int ans = AStar(start) ;
		printf("%d\n",ans) ;
	}
	return 0;
}