C++ 代码
注解:
map: map内部实现了一个红黑树,该结构具有自动排序的功能,因此map内部的所有元素都是有序的,红黑树的每一个节点都代表着map的一个元素,因此,对于map进行的查找,删除,添加等一系列的操作都相当于是对红黑树进行这样的操作,故红黑树的效率决定了map的效率。
unordered_map: unordered_map内部实现了一个哈希表,因此其元素的排列顺序是杂乱的,无序的
#include<iostream>
#include<algorithm>
#include<queue>
#include<unordered_map>//使用map会超时
using namespace std;
int bfs(string start)
{
string end = "12345678x";//设置搜索结束的状态,作为flag
queue<string> d;//存放每一个字符串的状态
unordered_map<string,int> st;//存放修改后的状态距离初始状态的距离
d.push(start);
st[start] = 0;
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
while(d.size()>0){//遍历栈中的字符串
auto t = d.front();//取出栈中的第一个字符串开始遍历
d.pop();//将第一个字符串进行出栈操作
int k = t.find('x');//找到x字符的位置
int distance = st[t];
int x=k/3,y=k%3;//找到字符'x'在3*3方格中的位置
if(t == end) return distance;
for(int u=0;u<4;u++){
int a = x+dx[u], b = y+dy[u];
if(a>=0&&a<3&&b>=0&&b<3){
swap(t[k],t[a*3+b]);
if(!st.count(t)){//如果字符串不在map中,就将该新的状态添加进去
st[t] = distance+1;
d.push(t);
}
swap(t[k],t[a*3+b]);
}
}
}
return -1;
}
int main()
{
string start;
for(int u=0;u<9;u++){//读取八数码的初态即一个字符串
char c;
cin>>c;
start+=c;
}
cout<<bfs(start)<<endl;
}