八数码难题————Astar算法好

八数码难题

//A*算法 +深搜 
//最优性剪枝有两个
//第一个是当前一定不是最优解见test
//第二个是当前状态在以前出现过见pre 
#include <iostream>
#include <cstdio>
using namespace std; 
char s[10];
bool judge;
int sta[4][4],x,y,k=2;
int ans[4][4]={{0,0,0,0},{0,1,2,3},{0,8,0,4},{0,7,6,5}};
//方向设成这样很有讲究
//把左右两步相加等于3，上下两步相加等于3
//如果说上一步是向左你这一步向右，或者是上一步向上这一步向下，就回到上次状态了吧？
//回到上次状态就重复了直接过滤return
//方便后面check 
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};
//判当前状态是否与目标状态吻合 
bool check(){
	for(int i=1;i<=3;i++)
	for(int j=1;j<=3;j++)
	if(ans[i][j]!=sta[i][j])return 0;
	return 1;
}
//最优性剪枝 
//如果当前状态和目标状态的不同点+已经走的步数>枚举的深度就不用走下去 
bool test(int step){
	int diff=0;
	for(int i=1;i<=3;i++)
	for(int j=1;j<=3;j++)
	if(ans[i][j]!=sta[i][j]){
		if(++diff+step>k)return 0; //在循环内部判，更好 
	} 
	return 1;
}
//算法核心
//第一步是看这个步骤到达没有 
void Astar(int step,int x,int y,int pre){
	if(step==k){
		if(check())judge=1;//这里不应该把check和step一起形成条件判断，因为这样的话到了k步还会一直搜下去 
		return;
	}
	if(judge)return;
	for(int i=0;i<4;i++){//四面广搜 
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx>3||nx<1||ny>3||ny<1||pre+i==3)continue;//这个就是那个判断有没有回到上次状态的请况，简直大佬！ 这个剪枝想不出来60顶天！ 
		swap(sta[nx][ny],sta[x][y]);
		if(test(step))Astar(step+1,nx,ny,i);
		swap(sta[nx][ny],sta[x][y]);
	}
}
int main() {
	scanf("%s",&s);
	for(int i=0;i<9;i++){
		sta[i/3+1][i%3+1]=s[i]-'0';
		if(s[i]-'0'==0){x=i/3+1;y=i%3+1;}
	}
	if(check()){
		printf("%d ",0);
		return 0;
	}
	while(++k){
		Astar(0,x,y,-1);
		if(judge){
			printf("%d",k);
			break;
		}
	}
	return 0;
}