有9只盘子，排成1个圆圈。
其中8只盘子内装着8只蚱蜢，有一个是空盘。
我们把这些蚱蜢顺时针编号为 1~8
每只蚱蜢都可以跳到相邻的空盘中，
也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，
并且保持空盘的位置不变（也就是1-8换位，2-7换位,...），至少要经过多少次跳跃？
参考 https://blog.csdn.net/monkey_rose/article/details/79769804
不难 但是写的心累 学习了string的用法 还有计算查重的时候不必把值给算出来 只需要往set里面丢string
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <algorithm>
int N, M, K;
//const int MAXN = , MAXM = 0;
//typedef long long ll;
//const int si =
using namespace std;
int cd[4] = {-1, -2, 1, 2};
string sta = "123456789";
string ans = "876543219";
set <string> st;
void bfs() {
queue <pair<string, int> > q;
q.push(make_pair(sta, 0));
while (!q.empty()) {
pair<string, int> pa = q.front(); q.pop();
string s = pa.first;
int cnt = pa.second;
if (s == ans) M = min(M, cnt);
if (st.count(s) != 0) continue;
st.insert(s);
//cout << s << endl;
int space = 0;
for( int i = 0; i < 9; i++) {
if (s.at(i) == '9') {
space = i;
break;
}
}
for(int i = 0; i < 4; i++) {
int np = space + cd[i];
i f (np >= 9) np -=9;
if (np < 0) np += 9;
string sss = s;
sss[space] = s[np];
sss[np] = s[space];
q.push(make_pair(sss, cnt + 1));
}
}
}
int main() {
N = 9;
M = 200000000;
bfs();
cout << M << endl;
return 0;
}
