记录编号	557468	评测结果	AAAAAAAAAA
题目名称	八数码问题	最终得分	100
用户昵称	tat	是否通过	通过
代码语言	C++	运行时间	1.334 s
提交时间	2020-11-16 19:10:02	内存使用	12.46 MiB

#include <bits/stdc++.h>
//A*
using namespace std;
struct node{
	int cost;//the cost so far
	int pc;//predicted cost
	string st;//state
	bool operator < (const node &tmp)const{
		return this->pc > tmp.pc ;
	}
	node (int a,int b,string c){
		pc=a;
		cost=b;
		st=c;
	}
}; 
int x,y;
map <string, bool>mp;   //映射   // 
map <string, int> dis;           // 
int dx[4] = {0, 1, -1, 0};//dfs常规上下左右 
int dy[4] = {1, 0, 0, -1};// 
string s;
char goal[10]="123804765"; 
int mubiao;
int gj(string cur){//估价函数
	int res = 0;
	for (int i = 0; i < 9; i ++ ){
		if (goal[i] != cur[i] && goal[i] != 0) res++;//不算上0 
	}
	return res;
} 
priority_queue<node> bfs;    
int main(int argc, char** argv) {
	freopen("bama.in","r",stdin);
	freopen("bama.out","w",stdout);
	cin>>s;
	for(int j=1,i=0;i<9;i++,j*=9){//计算目标的哈希值 
		mubiao+=(goal[i]-'0')*j;
	}
	if(gj(s)==0){//一开始就是目标状态 
		cout<<0<<endl;
		return 0;
	}

	for(int i = 0; i < 9; ++ i ) 
		if(s[i]-'0'==0)x=i/3+1,y=i%3+1;//确定零点的位置 
	//当前的估价函数，当前的步数，当前的状态 
	bfs.push(node(gj(s), 0, s));
	//
		mp[s] = 1;//s状态已经有过 
	    dis[s] = 0;//成为s状态的花费为0 
	//
	//ASTAR
	while(!bfs.empty()){
		node now=bfs.top();
		bfs.pop();
		string cur=now.st;
		int sx, sy;
		for(int i=0;i<9;i++){
	       	if(cur[i]-'0'==0)sx=i/3+1,sy=i%3+1;
		}//找当前0点
		 
		if(now.st==goal){
	        cout<<now.pc;
	        return 0;
		}//第一次出队列 
		int tmp1=(sx-1)*3+sy-1;//tmp1 ->当前零点位置 
		for(int i=0;i<4;i++){
			for (int i=0;i<4;i++){
				int xx=dx[i]+sx,yy=dy[i]+sy;			
				if (xx<1||xx>3||yy<1||yy>3) continue;//防越界 
				int tmp2 = (xx-1)*3+yy-1;//tmp2 ->接下来要走的位置 
					swap(cur[tmp1], cur[tmp2]);
				if (mp[cur] == 0 || (mp[cur] == 1 && (now.cost + 1) < dis[cur])) {
					dis[cur] = now.cost + 1;
					mp[cur] = 1;
					bfs.push((node){gj(cur) + now.cost + 1, now.cost + 1, cur}); 
				}
				swap(cur[tmp1], cur[tmp2]);//还原现场 
			}
		}
	}
	return 0;
}
//code