** Description of the problem
There are nine plates and eight grasshoppers, and each plate can only hold one grasshopper, the grasshoppers are numbered from 1 to 8, if the plate where the grasshopper is located is next to an empty plate, then the grasshopper can jump from its own plate to the empty plate, or jump to the empty plate one plate away, ask the state at the beginning of the state is 012345678, the grasshopper at least how many steps to jump before it can be changed into 087654321
**Input
not have
**Output
Steps skipped by grasshoppers
Problem Analysis:
The title says the grasshopper is jumping, but there are many grasshoppers, which will increase the difficulty of coding, but the empty plate is only one, we can let the plate move, you can then circumvent this problem, after analyzing the plate's movement in four ways, left 1, left 2, right 1, right 2, but because of the title of these plates is a circle, so the movement of this factor should be taken into account, which is what we often say to the curve into a straight! to mention one more, this move is actually a formula but I do not quite like to push, so I used the switch statement, the effect is the same!
After that is the core of the question ----- de-emphasis, here I use when the map, in fact, there are set, de-emphasis operation can help delete a large number of duplicate node
#include<iostream>
#include<map>
#include<queue>
using namespace std;
struct node {
node(){}
node(string ss, int tt,int po) :s(ss),t(tt),pos(po){}
string s;
int t; //Indicates the number of steps
int pos; //Indicates the current string0location，through (a gap)0Initial number
};
map<string, bool>mp;
queue<node>que;
node now, nxt;
int cal(int i,int pos) {
switch (i) {
case 1:
return pos + 1 > 8 ? pos+1-8-1 : pos + 1;
break;
case 2:
return pos + 2 > 8 ? pos+2-8-1 : pos + 2;
break;
case 3:
return pos - 1 < 0 ? pos-1+8+1 : pos - 1;
break;
case 4:
return pos - 2 < 0 ? pos-2+8+1 : pos - 2;
}
}
void bfs() {
while (!()) {
now = ();
();
//If you find the answer, end the loop.
if ( == "087654321") {
cout << << endl;
break;
}
for (int i = 1; i <= 4; i++) {
int k = cal(i, );
= k;
= ;
= + 1;
char tmp = [];
[] = [k];
[k] = tmp;
//mapsentence (sb) to a higher penalty
if (!mp[]) {
mp[] = true;
(nxt);
}
}
}
}
int main() {
string s = "012345678";
(node(s, 0, 0));
mp[s] = true;
bfs();
return 0;
}