179. 八数码（A*启发式搜索）

在一个?3×3 的网格中，1～8?这?8?个数字和一个?X?恰好不重不漏地分布在这?3×3 的网格中。

例如：

1 2 3
X 4 6
7 5 8

在游戏过程中，可以把?X?与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 X

例如，示例中图形就可以通过让?X?先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3   1 2 3   1 2 3   1 2 3
X 4 6   4 X 6   4 5 6   4 5 6
7 5 8   7 5 8   7 X 8   7 8 X

把?X?与上下左右方向数字交换的行动记录为?u、d、l、r。

现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

输入格式

输入占一行，将?3×3 的初始网格描绘出来。

例如，如果初始网格如下所示：

1 2 3 
x 4 6 
7 5 8 

则输入为：1 2 3 x 4 6 7 5 8

输出格式

输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。

如果答案不唯一，输出任意一种合法方案即可。

如果不存在解决方案，则输出?unsolvable。

输入样例：

2  3  4  1  5  x  7  6  8 

输出样例

ullddrurdllurdruldr

解析 ：

性质：当所给输入有答案的充分必要条件是输入的逆序对为偶数

对于估计距离，我们可以使用哈密顿距离作为估计距离?

A*算法为BFS的优化算法：?

2.1.3 BFS中的双向广搜和A-star - AcWing

?

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
string start, s;
typedef pair<int, string> PIS;

int F(string u) {
	int ret = 0;
	for (int i = 0; i < 8; i++) {
		int t = u[i] - '1';
		int x = i / 3, y = i % 3;
		ret += abs(x - t / 3) + abs(y - t % 3);
	}
	return ret;
}

string Astar() {
	char dir[] = "urdl";
	unordered_map<string, int>dist;
	unordered_map<string, pair<string, char>>pre;
	priority_queue<PIS, vector<PIS>, greater<PIS>>q;

	int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };

	dist[start] = 0;
	q.push({ dist[start],start });
	PIS t;
	while (!q.empty()) {
		t = q.top();
		q.pop();
		if (t.second == "12345678x")break;
		int x = 0, y = 0;
		for (int i = 0; i < t.second.size(); i++) {
			if (t.second[i] == 'x') {
				x = i / 3, y = i % 3;
				break;
			}
		}
		string tmp;
		for (int i = 0; i < 4; i++) {
			int a = x + dx[i], b = y + dy[i];
			if (a < 0 || a >= 3 || b < 0 || b >= 3)continue;
			tmp = t.second;
			swap(tmp[a * 3 + b], tmp[x * 3 + y]);
			if (dist.count(tmp) == 0 || dist[tmp] > dist[t.second] + 1) {
				dist[tmp] = dist[t.second] + 1;
				pre[tmp] = { t.second,dir[i] };
				q.push({ dist[tmp]+F(tmp),tmp});
			}
		}
	}

	string ret,tmp="12345678x";
	while (tmp != start) {
		ret += pre[tmp].second;
		tmp = pre[tmp].first;
	}
	reverse(ret.begin(), ret.end());
	return ret;
}

int main() {
	string ch;
	for (int i = 1; i <= 9; i++) {
		cin >> ch;
		if (ch != "x")s += ch;
		start += ch;
	}
	int cnt = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = i + 1; j < 8; j++) {
			if (s[i] > s[j])cnt++;
		}
	}
	//cout << cnt << endl;
	if (cnt & 1)cout << "unsolvable" << endl;
	else {
		cout << Astar() << endl;
	}

	return 0;
}

?本题直接暴搜也能过：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
string start, s;
typedef pair<int, string> PIS;

string Astar() {
	char dir[] = "urdl";
	unordered_map<string, int>dist;
	unordered_map<string, pair<string, char>>pre;
	priority_queue<PIS, vector<PIS>, greater<PIS>>q;

	int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };

	dist[start] = 0;
	q.push({ dist[start],start });
	PIS t;
	while (!q.empty()) {
		t = q.top();
		q.pop();
		if (t.second == "12345678x")break;
		int x = 0, y = 0;
		for (int i = 0; i < t.second.size(); i++) {
			if (t.second[i] == 'x') {
				x = i / 3, y = i % 3;
				break;
			}
		}
		string tmp;
		for (int i = 0; i < 4; i++) {
			int a = x + dx[i], b = y + dy[i];
			if (a < 0 || a >= 3 || b < 0 || b >= 3)continue;
			tmp = t.second;
			swap(tmp[a * 3 + b], tmp[x * 3 + y]);
			if (dist.count(tmp) == 0 || dist[tmp] > dist[t.second] + 1) {
				dist[tmp] = dist[t.second] + 1;
				pre[tmp] = { t.second,dir[i] };
				q.push({ dist[tmp],tmp });
			}
		}
	}

	string ret,tmp="12345678x";
	while (tmp != start) {
		ret += pre[tmp].second;
		tmp = pre[tmp].first;
	}
	reverse(ret.begin(), ret.end());
	return ret;
}

int main() {
	string ch;
	for (int i = 1; i <= 9; i++) {
		cin >> ch;
		if (ch != "x")s += ch;
		start += ch;
	}
	int cnt = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = i + 1; j < 8; j++) {
			if (s[i] > s[j])cnt++;
		}
	}
	//cout << cnt << endl;
	if (cnt & 1)cout << "unsolvable" << endl;
	else {
		cout << Astar() << endl;
	}


	return 0;
}