玛雅人有一种密码，如果字符串中出现连续的 2012 四个数字就能解开密码。

给定一个长度为 N 的字符串，该字符串中只含有 0,1,2 三种数字。

可以对该字符串进行移位操作，每次操作可选取相邻的两个数字交换彼此位置。

请问这个字符串要移位几次才能解开密码。

例如 02120 经过一次移位，可以得到 20120,01220,02210,02102，其中 20120 符合要求，因此输出为 1。

如果无论移位多少次都解不开密码，输出 −1。

输入格式
第一行包含一个整数 N，表示字符串的长度。

第二行包含一个由 0,1,2 组成的，长度为 N 的字符串。

输出格式
若可以解出密码，则输出最少的移位次数；否则输出 −1。

数据范围
2≤N≤13
输入样例：
5
02120
输出样例：
1

BFS 模板题，只需要把字符串当作当前状态，交换相邻两个字符进入下一个状态，第一个找到带有2012的字符串就是移动次数最少的

#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
int n;
string s;
unordered_map<string,int> cnt;//标识该字符串的移动次数
queue<string> q;
int bfs(string s)
{if(s.find("2012")!=string::npos) return 0;q.push(s);cnt[s]=0;while(!q.empty()){string t=q.front();q.pop();string s=t;for(int i=1; i<n; i++){swap(t[i],t[i-1]);if(!cnt.count(t))//判断是否已经搜索{cnt[t]=cnt[s]+1;//更新移动次数q.push(t);if(t.find("2012")!=string::npos) return cnt[t];}swap(t[i],t[i-1]);//恢复状态}}return -1;
}int main()
{cin>>n>>s;cout<<bfs(s);
}