如图 p1.png 所示： 有9只盘子，排成1个圆圈。 其中8只盘子内装着8只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 1~8
每只蚱蜢都可以跳到相邻的空盘中， 也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列， 并且保持空盘的位置不变（也就是1-8换位，2-7换位,…），至少要经过多少次跳跃？
把空盘看作9，求最小步数，即BFS状态转移到目标态需要的最小步数，祥见代码，很清晰。 标记vis数组用bool不是int ,bool更快。 蚱蜢的跳跃即数字的交换，用arr数组解决，swap容易交换。用arr数组表示数字涉及到数组再转化为数字的问题。
int s = 123456789;//9代表空盘 int t = 876543219;//目标状态 bool vis[1000000000];//标记此状态存在与否 int dir[4] = {-2,-1,1,2};//四种移动方式 int arr[10];//用来按位存储当前状态的数组 typedef struct node { int now;//当前九位数字状态 int stepcnt;//步数记录 }Node; queue<Node>q; int GetarrVal()//把arr数组中的值转化为一个9位数字 { int sum=0; for(int i=0; i<9; i++) { sum*=10; sum+=arr[i]; } return sum; } int main() { node a1; a1.now = s; a1.stepcnt = 1; q.push(a1);//把初始状态入队 while(!q.empty()) { memset(arr,0,sizeof(arr)); node a = q.front(); int nowstate = a.now;//记录当前状态，即9位数字 int nowstep = a.stepcnt;//记录到当前状态的步数 int nullpos;//记录空盘的位置 q.pop(); //获取空盘的位置,并把当前的状态按位存入数组中，便于交换 int cnt = 8;//往arr数组存入当前状态的9位数字， while(nowstate>0) { if(nowstate%10==9)//当前位置是空盘 { nullpos = cnt;//记录空盘位置 } arr[cnt--] = nowstate%10; nowstate/=10; } //从空盘左1,从空盘右1，从空盘左2，从空盘右2共四种跳法 for(int i=0;i<4;i++) { swap(arr[nullpos],arr[(nullpos-dir[i]+9)%9]);//交换空盘与要移动点的位置 int num = GetarrVal(); if(!vis[num]) { if(num == t) { cout<<nowstep<<endl; } vis[num] = 1; node a2 ; a2.now = num , a2.stepcnt = nowstep+1; q.push(a2); } swap(arr[nullpos],arr[(nullpos-dir[i]+9)%9]);//注意交换完要再换回去，保证四次交换的num一样 } } }