原题链接
题解
要求最小的交换次数，那么就可以使用bfs来做，可以把每一次的交换之后的图抽象成一个节点，那么每次转移状态就相当于向下一个节点走，走过的边的权重为1(不是在原来的3*3的图上做bfs)，这样就可以使用dfs做了
需要解决的问题是：
①每一个状态该如何表示
②如何记录每个状态的距离
③什么情况下表示不能后形成最终的状态
解决方式
①可以把二维数组转化成字符串的形式，每一步形成的字符串就是一个状态（每一个状态不要重复的经过，判定就好）
②因为是使用的字符串表示的状态，以前做bfs的时候，都是单一的点或者是坐标，这里就使用哈希表的方式，将字符串转化成对应的下标（以后这种类似的情况下类比也可以使用哈希表的方式）
③当队列为空了，还是没有找到最终状态，就表示不能够达到这个最终的状态（因为已经将所有的状态枚举了）
接下来就是常规的dfs的过程了，这道题最难的地方就在于上述的几点以及抽象的表示
图示
代码如下
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
int bfs(string start){
string end = "12345678x";//定义最终状态
queue<string> q;
unordered_map<string, int> dis;
int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};
q.push(start); dis[start] = 0;
while(q.size()){
auto t = q.front(); q.pop();
if(t == end) return dis[t];
int j = t.find(‘x‘);
for(int i = 0; i < 4; ++i){
//这里还是转化成二维数组做方便一点，因为直接在字符串中x的左右最近的点不一定能够走到还又要判定
int x = j / 3 + dx[i], y = j % 3 + dy[i];
if(x >= 0 && x < 3 && y >= 0 && y < 3){
string s = t;
swap(s[x * 3 + y], s[j]);
if(!dis.count(s)){
dis[s] = dis[t] + 1;
q.push(s);
}
}
}
}
return -1;
}
int main(){
string start;
for(int i = 0; i < 9; ++i){
char ch; cin >> ch;
start += ch;
}
cout << bfs(start) << endl;
return 0;
}
这个题目中，每一个变化都是代表着一种状态，难在不知道如何表示状态（这里是使用字符串表示每一个图），当把所有的状态枚举结束之后，还是没有出现结果，此时说明了这个输入的初始状态是不能够转化成最终的状态。搜索并不一定要在现有的图上做，如果每一步会改变图，就可以把每一次改变的图抽象成一个结点，用某一种状态去表示，然后结点和结点之间就构成了一张新的图。