八数码

题目链接：https://www.acwing.com/problem/content/847/

题目描述

在一个 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
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入描述

输入占一行，将 3×3 的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8

输出描述

输出占一行，包含一个整数，表示最少交换次数。
如果不存在解决方案，则输出 −1。

示例

输入

2 3 4 1 5 x 7 6 8

输出

19

分析

既然题目要求的是最小交换次数，我们就可以首先排除DFS(一般不用来求最小值)，选择BFS。
让我们试着将本题向BFS求最短路径的方向迁移。
显然，本题存在如下性质：

• 网格的每一种状态可以看作是一个节点
• 相邻状态的迁移只需要1步

这恰恰就是BFS求解最短路径的模型。
本题的难点在于如何去表示这个状态。考虑一下，可以用string来表示，比如：
1 2 3
x 4 6
7 5 8
用string表示就是”123x46758”。
同时，我们采用unordered_map来表示从初始状态转移到当前状态最少需要几步。
之后，这个问题就转换成了BFS求最短路的问题了。

AC代码

---

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <unordered_map>

using namespace std;

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

int bfs(string start)
{
	queue<string> q;
	unordered_map<string, int> d;
	q.push(start);
	d[start] = 0;
	while (!q.empty())
	{
		string a = q.front();
		int distance = d[a];
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int pos = a.find('x');
			int x = pos / 3, y = pos % 3;
			int newx = x + dx[i], newy = y + dy[i];
			if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3)
			{
				swap(a[3 * x + y], a[3 * newx + newy]);
				if (!d.count(a))
				{
					d[a] = distance + 1;
					if (a == "12345678x")
						return d[a];
					q.push(a);
				}
				swap(a[3 * x + y], a[3 * newx + newy]);		//不要忘了还原
			}
		}
	}
	return -1;
}

int main()
{
	string start;
	for (int i = 0; i < 9; i++)
	{
		char temp;
		cin >> temp;
		start += temp;
	}
	cout << bfs(start) << endl;
	return 0;
}