原题在这里P1379 八数码难题

思路：

本题的思路很有意思，首先我们知道0是可以和上下左右交换位置的（前提是不出边界）

        不难看出我们可以把这个二维数组给转化为一个相对应的字符串来表示当前的状态，每进行一次，就将操作次数+1，然后我们在这个过程中所要到达的目标状态为123804765。那其实我们会发现其实就是BFS求最短路径问题，因为边权相同。

        那具体实现就是将每一个状态都用字符串来记录，接着用under_map容器（Hash表）来记录当前状态所花费的步数。

那到这又会出现一个问题，一维又该怎么转回二维呢？

一维坐标k转换成n*m的二维坐标x,y:x=k/n,y=k%m反之k=x*n+m

#include <iostream>
#include <cstring>
#include <unordered_map>
#include <queue>
using namespace std;

int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };//记录方向的数组 
queue<string> q;//记录最短路径的的状态变化
unordered_map<string, int> step;//用于记录初始状态到当前这个状态所用的步数

int bfs(string start) {
	q.push(start);//start入队
	step[start] = 0;//初始状态到初始状态的步数当然是0
	string end = "123804765";//目标状态

	while (q.size()) {
		auto tmp = q.front();
		q.pop();
		int distance = step[tmp];//对头距离记录为distance
		if (tmp == end) return distance;//搜到终点就返回最短距离
		int k = tmp.find('0');//找到0所在的位置
		int x = k / 3, y = k % 3;//将一维的点转化为二维的点的坐标 
		for (int i = 0; i < 4; i++) {
			int tox = x + dx[i], toy = y + dy[i];//将对头扩展，寻找状态 
			if (tox >= 0 && tox < 3 && toy >= 0 && toy < 3) {//如果未出边界，那么就扩展 
				swap(tmp[k], tmp[tox * 3 + toy]);//交换x和上下左右的位置 
				if (!step.count(tmp)) {//如果这种状态之前没有出现过，那么就更新step距离 
					step[tmp] = distance + 1;
					q.push(tmp);//将t入队 
				}
				swap(tmp[k], tmp[tox * 3 + toy]);//不要忘了恢复原状态 
			}
		}
	}
	return -1;//如果实在搜不到，那就返回-1 
}
int main() {
	string s;
	for (int i = 0; i < 9; i++) {//将其整合成一个字符串，表示当前的状态
		char c;
		cin >> c;
		s += c;
	}
	cout << bfs(s) << endl;
	return 0;
}

当然，这题用A*也能做啊，不过俺不会，u can looklook大佬的

A*算法解决八数码