算法题：玛雅人的密码

题目描述

玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=<N<=13）该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。

输入描述

输入包含多组测试数据，每组测试数据由两行组成。

第一行为一个整数N，代表字符串的长度（2<=N<=13）。

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

输出描述:

对于每组测试数据，若可以解出密码，输出最少的移位次数；否则输出-1。

示例

输入

5
02120

输出

1

题解：这道题使用BFS即可解决，相关注释已写在代码内

#include <bits/stdc++.h>  
using namespace std;
struct Status{
    string s;    //字符串
    int num;    //移动次数 
    Status(string s,int num):s(s),num(num){}
};

string Swap(string str, int i){    //交换字符串i,i+1位置 
    swap(str[i], str[i + 1]);
    return str;
}

bool isVaild(string str){    //判断是否符合题意 
    return str.find("2012") != string::npos;
} 

int BFS(string str){    //广度优先 
    queue<Status> Q;    //广度优先队列 
    map<string, bool> M;//用来判断str是否被检查过的 
    Q.push(Status(str,0)); 
    M[str] = true;
    while(!Q.empty()){
        Status current = Q.front();    //队首 
        Q.pop();
        M[current.s] = true;
        if(isVaild(current.s)) return current.num;    //如果合法，直接返回次数 
        //不合法，把移动一次后所有可能压入队 
        for(int i = 0; i < str.size()-1; i++){
            string new_str = Swap(current.s, i);    //移动一次 
            if(M[new_str] == false)    //如果移动一次后的没有判断过 
                Q.push(Status(new_str, current.num + 1));    //压入
            //else 判断过，不用入队 
        }
    }
    return -1;    //如果所有情况判断完，仍然没找到，返回-1 
}

int main(){
    int N;
    string input;
    cin >> N >> input;
    cout << BFS(input);
    return 0;
}