題目描述
你獲得了一個據說是古代瑪雅人制作的箱子。你非常想打開箱子看看里面有什么東西,但是不幸的是,正如所有故事里一樣,神秘的箱子出現的時候總是會掛著神秘的鎖。
這個鎖上面看起來有 N 個數字,它們排成一排,并且每個數字都在 0 到 2 之間。你發現你可以通過鎖上的機關來交換相鄰兩個數字的順序。比如,如果原來有 5 個數字 02120,在一次交換以后你就可以得到 20120,01220,02210 或者 02102。
根據你所搜集的情報,這個鎖在上面存在某連續四個數字是“2012”的時候會自動打開。現在,你需要計算一下,你至少需要進行多少次交換操作才能打開這把鎖?

對樣例的解釋
把前兩個數字交換以后,鎖上的數字是 20120,其中存在連續四個數字2, 0, 1, 2,因此鎖會打開。

輸入
輸入數據的第一行有一個正整數 N。(4 ≤ N ≤ 13) 輸入數據的第二行有 N 個數字 a1,a2, …, aN ,其中 ai 表示這個鎖上面第 i 個數字的值,滿足 0 ≤ ai ≤ 2。這些數字之間沒有空格分隔。
輸出
你只需要輸出一個數字,即你至少需要的交換次數。如果無論如何都沒有希望打開這把鎖,輸出 -1。
樣例輸入
5
02120
樣例輸出
1
思路：一個比較基礎的BFS題目，這里用到了string中的find函數。如果在s中存在“2012”這個串，那么就會返回這個串的第一個字符的下標，否則就會返回-1.
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; struct node{string s;int num;node(string tt,int a){s=tt,num=a;} }; string s; int n;inline int bfs() {map<string,bool> mp;queue<node> q;mp[s]=1;q.push(node(s,0));string tt;while(q.size()){node u=q.front();q.pop();if(u.s.find("2012")!=-1) return u.num;tt=u.s;for(int i=0;i<tt.length()-1;i++){swap(tt[i],tt[i+1]);if(mp[tt]==0){mp[tt]=1;q.push(node(tt,u.num+1));}swap(tt[i],tt[i+1]);}}return -1; } int main() {cin>>n>>s;cout<<bfs()<<endl;return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的[蓝桥杯][算法提高VIP]密码锁(BFS)的全部內容，希望文章能夠幫你解決所遇到的問題。

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