問題描述

有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; }

求三連 求三連！ 啊！我第一個給博主三連！

總結

以上是生活随笔為你收集整理的45行代码AC_2017年第八届蓝桥杯C/C++ A组第二题（广搜模板+解题报告）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。