有9只盤(pán)子，排成1個(gè)圓圈倦逐。
其中8只盤(pán)子內(nèi)裝著8只蚱蜢譬正，有一個(gè)是空盤(pán)。
我們把這些蚱蜢順時(shí)針編號(hào)為 1~8
每只蚱蜢都可以跳到相鄰的空盤(pán)中檬姥，
也可以再用點(diǎn)力曾我，越過(guò)一個(gè)相鄰的蚱蜢跳到空盤(pán)中。
請(qǐng)你計(jì)算一下健民，如果要使得蚱蜢們的隊(duì)形改為按照逆時(shí)針排列抒巢，
并且保持空盤(pán)的位置不變（也就是1-8換位，2-7換位,...）秉犹，至少要經(jīng)過(guò)多少次跳躍蛉谜？
參考 https://blog.csdn.net/monkey_rose/article/details/79769804
不難 但是寫(xiě)的心累 學(xué)習(xí)了string的用法 還有計(jì)算查重的時(shí)候不必把值給算出來(lái) 只需要往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;
}
