答案是：20
#include<stdio.h> #include<math.h> #include<algorithm> #include<string.h> #include<iostream> #include<set> #include<queue> #define ll long long using namespace std; ///几秒可以出答案，但是有时间限制就不行了，但幸好这是一道填空题 set<string>vis;///已经搜索过的局面 剪枝，降低复杂度 struct node { int pos; ///o的位置，也就是空盘子的位置 int step;///到达这个局面的步数 string str;///局面字符串 }; queue<node>q; ///用来广搜的队列 void bfs(node nex,int i) ///nex为新的局面，i为移动方式 { string s=nex.str; swap(s[nex.pos],s[(nex.pos+i+9)%9]); ///取模是为了模拟循环的数组 if(vis.count(s)==0)///如果没有搜索过这个局面 { vis.insert(s); node nexx; nexx.str=s; nexx.pos=(nex.pos+i+9)%9; nexx.step=nex.step+1; q.push(nexx); } } int main() { vis.clear(); node first; first.pos=0; first.step=0; first.str="012345678"; q.push(first); while(!q.empty()) { node nex; nex=q.front(); if(nex.str=="087654321") { printf("%d\n",nex.step); break; } else { ///四种跳法 bfs(nex,1); bfs(nex,-1); bfs(nex,2); bfs(nex,-2); q.pop(); } } }