八数码难题（ A*算法详解，附题目链接 ）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include<iostream>
#include<queue>
#include<utility>
#include<map>
#include<cmath>
#include<windows.h> 
#define mp(x,y) make_pair(x,y)

using namespace std;

//输入两个长度为9的数字串，分别代表初始状态和目标状态

typedef struct node{//定义节点为目前棋盘状态
	pair<int,int> center;
	int g[4][4];
}node;

bool operator == (node x,node y){//用于比较节点是否相同
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			if(x.g[i][j]!=y.g[i][j])return 0;
		}
	}
	return 1;
}

bool operator < (node x,node y){//用于查找节点
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			if(x.g[i][j]<y.g[i][j])return 1;
			else if(x.g[i][j]>y.g[i][j])return 0;
		}
	}
	return 0;
}

void init_node(node &x){//初始化节点
	for(int i=0;i<=3;i++)
	{
		for(int j=0;j<=3;j++)
		{
			x.g[i][j]=0;
		}
	}
}

char o1[15],o2[15];//输入初始状态与目标状态

node s,e;

priority_queue< pair<int,node> > q;

map<node,int> g; //用于记录状态是否出现过，避免重复搜索

map<node,node> pre; //记录前驱节点

int dx[4]={-1,0,1,0};//搜索的四个方向
int dy[4]={0,1,0,-1};

int cal_h(node x)//计算启发函数（两个状态各个数位曼哈顿距离的和）
{
	int sum=0;
	pair<int,int> h[9];//预处理优化
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			h[x.g[i][j]]=mp(i,j);
		}
	}
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			sum+=abs(i-h[e.g[i][j]].first)+abs(j-h[e.g[i][j]].second);
		}
	}
	return sum;
}

void print_mp(node x)//输出当前状态
{
	system("cls");
	for(int i=1;i<=4;i++)cout<<"n";
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=6;j++)cout<<"t";
		for(int j=1;j<=3;j++)
		{
			cout<<x.g[i][j]<<"  ";
		}
		cout<<"nn";
	}
	Sleep(1000);
}

void print(node x)//递归输出
{
	if(x==s)print_mp(x);
	else{
		print(pre[x]);
		print_mp(x);
	}
}

int main()
{
	cin>>o1+1;
	cin>>o2+1;
	
	init_node(s);//将输入转化为节点状态
	for(int i=1;i<=9;i++)
	{
		s.g[(i+2)/3][(i-1)%3+1]=o1[i]-'0';
		if(s.g[(i+2)/3][(i-1)%3+1]==0)s.center=mp((i+2)/3,(i-1)%3+1);
	}
	
	init_node(e);
	for(int i=1;i<=9;i++)
	{
		e.g[(i+2)/3][(i-1)%3+1]=o2[i]-'0';
		if(e.g[(i+2)/3][(i-1)%3+1]==0)e.center=mp((i+2)/3,(i-1)%3+1);
	}
	
    //广搜，优先队列优化
	g[s]=0;
	
	q.push(mp(-(cal_h(s)+g[s]),s));
	
	while(!q.empty())
	{ 
		node tmp=q.top().second;
		q.pop();
		if(tmp==e)break;
		if(g[tmp]==25)//如果搜索的次数过多，结束搜索
		{
			cout<<"-1"<<endl;
			return 0;
		}
		int x=tmp.center.first;
		int y=tmp.center.second;
		for(int i=0;i<=3;i++)
		{
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(xx>=1&&xx<=3&&yy>=1&&yy<=3)
			{
				node u=tmp;
				swap(u.g[x][y],u.g[xx][yy]);
				if(g.find(u)==g.end())//如果没搜索过该状态，将其入队
				{
					u.center=mp(xx,yy);
					g[u]=g[tmp]+1;
					pre[u]=tmp;
					q.push(mp(-(cal_h(u)+g[u]),u));
				}
			}
		}
	}
	
	print(e);
	
	return 0;
}