跳蚱蜢 蓝桥杯

蚱蜢 蓝桥杯"/>

跳蚱蜢 蓝桥杯

蓝桥杯2017 C/C++ A组第2题
题目： 有9只盘子，排成1个圆圈。 其中8只盘子内装着8只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 1~8
每只蚱蜢都可以跳到相邻的空盘中， 也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列， 并且保持空盘的位置不变（也就是1-8换位，2-7换位,...），至少要经过多少次跳跃？
答案：20

利用广度优先遍历。

#include<iostream>
#include<queue>
using namespace std;
int kong;//空盘的位置
int state[10];
queue<int> q;
queue<int> Count;
int dir[4] = { -2,-1,1,2 };
bool visited[876543211] = { 0 };
void setState(int dishs) {for (int i = 8; i>=0; i--) {if (dishs % 10 == 0) {kong = i;}state[i] = dishs % 10;dishs = dishs / 10;}}
int getValue() {int array = 0;for (int i = 0; i<9; i++) {array = array * 10 + state[i];}return array;
}
bool extend() {int num = q.front();if (num == 87654321)return false;if (visited[num])return true;visited[num] = true;setState(num);for (int i = 0; i<4; i++) {state[kong] = state[(kong + dir[i] + 9) % 9];//移动空盘子 state[(kong + dir[i] + 9) % 9] = 0;q.push(getValue());//将移动后的盘子位置压入队列内 Count.push(Count.front() + 1);//将其对应的移动次数压入队列 setState(num);}return true;
}int main() {setState(12345678);Count.push(0);q.push(12345678);while (extend() && !Count.empty()) {q.pop();Count.pop();}cout << Count.front();return 0;
}