样例
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
unordered_map[HTML_REMOVED]d;//利用map存储每一个节点对应的距离
queue[HTML_REMOVED]que;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int bfs(string start){
string end=”12345678x”;
que.push(start);
d[start]=0;
while(que.size()){
auto t=que.front();
que.pop();
int distance=d[t];
if(t==end) return distance;
int k=t.find(‘x’);
int x=k/3,y=k%3;
for(int i=0;i<4;i){
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0&&ny>=0&&nx<3&&ny<3){
swap(t[k],t[3nx+ny]);
if(!d.count(t)) {
d[t]=distance+1;
que.push(t);
}
swap(t[k],t[3nx+ny]);
}
}
}
return -1;
}
int main(){
string start,c;
for(int i=0;i<9;i){
cin>>c;
start+=c;
}
cout<<bfs(start)<<endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla