[数据结构与算法]AcWing 845 八数码 题解（BFS）

题很巧妙，之前我还真不知道可以把矩阵问题换算到队列，用一维数组、队列解决（可能因为我太菜了），这个题的思路是真的巧妙
原题链接：https://www.acwing.com/problem/content/847/
解题思路：把不同的矩阵状态转化为一维字符串表示，从第一个初始矩阵开始，把每个可以达到的矩阵状态存入队列，挨个将队首元素出队，判断这个矩阵能达到的状态，将可以达到的状态入队，直到达到最终状态

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>//存字符串和距离的映射关系
#include<queue>//用队列存每个状态 

using namespace std;

int bfs(string start){
	
	string end = "12345678x";//标记最终想要达到的状态 
	unordered_map<string, int>d;
	queue<string>q;//字符串队列，储存每个矩阵状态 
	
	q.push(start);//将初始矩阵入队 
	//移动数组 
	int dx[4] = {0, 0, 1, -1}; 
	int dy[4] = {1, -1, 0, 0};
	
	while(q.size()){//当数组不空时 
		auto t = q.front();//队首元素出队 
		q.pop();
		
		if(t == end) return d[t];//如果此时队首元素已经达到end状态 
		
		int dis = d[t];//记录这个队首元素的步数值 
		int k = t.find('x');//找到一维数组中x的位置 
		int x = k % 3;//一维数组下标 %3是x点在矩阵中的横坐标 
		int y = k / 3;//一维数组的下标/3是x点在矩阵中的纵坐标 
		
		for(int i = 0; i < 4; i ++ ){//遍历x点要去的位置 
			int x1 = x + dx[i];
			int y1 = y + dy[i];
			
			if(x1 >= 0 && x1 < 3 && y1 >= 0 && y1 < 3){//如果x点可以到达这个位置 
				swap(t[k], t[y1 * 3 + x1]);//交换x点和目标位置 
				if(!d.count(t)){//如果交换后的矩阵没有出现过 
					d[t] = dis + 1;//交换后的矩阵对应的步数+1 
					q.push(t);//将交换后的矩阵入队 
				}
				swap(t[k], t[y1 * 3 + x1]);//判断这个状态入队之后恢复矩阵，因为要进行四次循环判断四个位置 
			}
		}
	}
	return -1;//如果一直没有找到合适的位置，就输出-1 
}

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