問題描述
有9只盤子，排成1個圓圈。
其中8只盤子內裝著8只蚱蜢，有一個是空盤。
我們把這些蚱蜢順時針編號為 1~8
每隻蚱蜢都可以跳到相鄰的空盤中，
也可以再用點力，越過一個相鄰的蚱蜢跳到空盤中。
請你計算一下，如果要使得蚱蜢們的隊形改為按照逆時針排列，
並且保持空盤的位置不變（也就是1-8換位，2-7換位,…），至少要經過多少次跳躍？
給出結論： 對於從某一狀態轉換到另一狀態，問最少需要多少步， 不出意外都是廣搜。
廣搜的優勢在於：第一次遍歷到的結果，一定就是最短路徑或最少步數，特殊型別題除外。
接下來考慮本題
首先， 將盤子們看做一個一維陣列， 通過取餘的方式使他們邏輯上相連。
接下來，構造佇列，將盤子的初始狀態入隊，分四種情況(+1, +2 , -1 , -2 )進行廣搜， 將得到的結果判重後入隊。
判重的原因是：有可能搜尋到相同排列順序的盤子們， 因此要定義判重陣列， 或使用mep容器去重。
藍橋杯的廣搜題真的挺少的， 不過套模板一般都能很輕鬆的解出來。
#include<bits/stdc++.h>
using namespace std;
int s = 123456789, t = 876543219;
int dir[4] = {-2, -1, 1, 2}, a[10];
bool index[1000000000]; //判斷情況是否重複
int num(int a[]) { //陣列轉變數
int sum = 0;
for(int i = 0; i < 9; i++) {
sum *= 10; sum += a[i];
}
return sum;
}
void bfs() {
queue<int>q_index; //記錄位置情況
queue<int>q_step; //記錄步數
//佇列初始化
index[s] = 1;
q_index.push(s);
q_step.push(1);
int flag = 0;
while(flag != 1) {
int x = q_index.front(); //出隊操作
int cnt = q_step.front();
int k = 8, temp;
while(x>0) {
if(x%10==9) temp=k; //記下空盤的位置
a[k--] = x%10;
x /= 10;
}
for(int i = 0; i < 4; i++) {
swap(a[temp], a[(temp+dir[i]+9)%9]); //位置移動
int j = num(a);
if(!index[j]) {
if(j==t) { cout<<cnt<<'\n'; flag=1; }
index[j] = 1;
q_index.push(j);
q_step.push(cnt+1);
}
swap(a[temp], a[(temp+dir[i]+9)%9]); //空盤一共需要跳四次，因此交換後還需換回來
}
q_index.pop();
q_step.pop();
}
}
int main() {
bfs();
return 0; }
求三連 求三連！ 啊！我第一個給博主三連！