#include <stdio.h>
#include <queue>
#include <string>
#include <iostream>
using namespace std;

bool pan(string a,int n) {
     bool flag=false;
     for(int i=0; i<n-3; i++) {
        if(a[i]=='2'&&a[i+1]=='0'&&a[i+2]=='1'&&a[i+3]=='2') {
            flag=true;
            break;
        }
    }
    return flag;
}

string swap(string a,int i,int j) {
    char temp=a[i];
    a[i]=a[j];
    a[j]=temp;
    return a;
}

struct E {
    string a;
    int t;
};
queue<E> Q;
int BFS(int n) {
    while(Q.empty()==false) {
        E now=Q.front();
        Q.pop();
        if(pan(now.a,n)){
            return now.t;
        }
        else{
            for(int i=0; i<n-1; i++) {
                string new_a=swap(now.a,i,i+1);
                int new_t=now.t+1;
                if(new_t>20) {
                    return -1;
                } else {
                    if(pan(new_a,n)) {
                        return new_t;
                    } else {
                        E tmp;
                        tmp.a=new_a;
                        tmp.t=new_t;
                        Q.push(tmp);
                    }
                }
            }
        }
    }
    return -1;
}
int main() {
    int n;
    string str;
    while(cin>>n>>str) {
        while(Q.empty()==false){
            Q.pop();
        }
        E tmp;
        tmp.a=str;
        tmp.t=0;
        Q.push(tmp);
        int ans=BFS(n);
        printf("%d\n",ans);
    }
    return 0;
}

#include<iostream>
#include<string>
#include<map>
#include<queue>
using namespace std;
int n;
bool judge(string s)
{
	int l=s.size();
	for(int i=0;i<l-3;i++)
	{
		if(s[i]=='2'&&s[i+1]=='0'&&s[i+2]=='1'&&s[i+3]=='2')
		{
			return true;
		}
	}
	return false;
}
int bfs(string s)
{
	map<string,int>mp;//如果遍历过，将second标记为1
	mp.clear();//清空上一次的缓存
	queue<pair<string,int>>que;//用队列来保存搜索的路径
	que.push(make_pair(s,0));//将第一个string入队
	while(!que.empty())//如果遍历过所有string,返回-1
	{
		pair<string,int> now=que.front();
		que.pop();//队头的string出队
		string str=now.first;
		if(judge(str))
			return now.second;
		if(mp[str])//如果该排列已经judge过，则跳到下一个排列
			continue;
		mp[str]=1;//如果没有就标记为已遍历过
		for(int i=0;i<n-1;i++)//创建新的排列
		{
			swap(str[i],str[i+1]);
			que.push(make_pair(str,now.second+1));
			swap(str[i],str[i+1]);
		}
	}
	return  -1;
}
int main()
{
	string s;
	while(cin>>n)
	{
		cin>>s;
		cout<<bfs(s)<<endl;
	}
	return 0;
}

经典的bfs搜索

#include<iostream>
#include<queue>
#include<map>
#include<string>


using namespace std;

char Aim[] = "2012";

typedef struct str_cos{     string str;                             //包含的字符串     int deep;                                //标示该串做了几次字符交换     str_cos(string str,int deep) {         this->deep = deep;         this->str = str;     }
}STR;

bool SubString(string S){  //判断某个字符串是否包含子串"2012"     int p = 0;     int q = 0;     while(p < S.size()){         if(S[p] == Aim[q]){             q++;         }         else{             q = 0;                     }         p++;         if(q == 4)             return true;     }     return false;
}

int MoveCounter(STR str){     queue<STR> Q;     map<string, int> MAP;          //用来区分该串是否之前已经生成过     char T;     int Length = str.str.size();     string S_temp;     Q.push(str);                   //原始串入队，为接下来的广度遍历做准备     MAP[str.str] = 1;              //标示原始串已经访问过，1是看心情给的     while (!Q.empty()) {         STR F_temp = Q.front();             Q.pop();         if (SubString(F_temp.str))                               //若该串满足题目要求，则输出深度（字符交换次数）             return F_temp.deep;         for (int i = 0; i < str.str.size() - 1; ++i) {           //该循环是用来把当前串的所有可能的相邻交换（一次）列出来             S_temp = F_temp.str;             T = S_temp[i];             S_temp[i] = S_temp[i + 1];             S_temp[i + 1] = T;             if (MAP.find(S_temp) == MAP.end()) {                 //若该交换后的新串先前木有出现过，则标示已访问，并入队。                 MAP[S_temp] = 1;                 Q.push(str_cos(S_temp, F_temp.deep + 1));             }         }     }     return -1;      }

int main(){     string S;     int N;     while(scanf("%d",&N) != EOF){   //这个N你可以看心情给！         cin>>S;         printf("%d\n",MoveCounter(str_cos(S,0)));     }     return 0;
}

	

/*
 * QQ:	825580813
 * 把所有的转换后的字符串都列出来,然后判断这其中是否包含"2012"即可.
 * 
 * 那么如何把他们都列出来呢?
 * 
 * 建立一张图,根据宽度优先遍历即可,(按理说,图有两种遍历,为何偏偏选择宽度优先呢)
 * 因为,这张图的建立过程与遍历过程同时进行.
 * 
 * 建立图的方法:
 * 		将源字符串作为第一个节点, 然后将它的移位字符串作为邻接点即可.
 */
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class StringNum{
	String str;
	int num;
	public StringNum(String str, int num) {
		this.str = str;
		this.num = num;
	}
}

public class MayanCode {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			String code = sc.next();
			int moveTime = getMoveTime(code, n);
			System.out.println(moveTime);
		}
		sc.close();
	}

	private static int getMoveTime(String code, int n) {
		if (n < 4) {
			return -1;
		}
		ArrayList<String> record = new ArrayList<>();
		Queue<StringNum> que = new LinkedList<>();
		StringNum stringNum = new StringNum(code, 0);
		que.offer(stringNum);
		record.add(code);
		while (!que.isEmpty()) {
			stringNum = que.remove();
			if (stringNum.str.contains("2012")) {
				return stringNum.num;
			}
			for (int i = 0; i < n - 1; ++i) {
				char[] temp = stringNum.str.toCharArray();
				swap(temp, i, i + 1);
				String tempStr = new String(temp);
				if (!record.contains(tempStr)) {
					record.add(tempStr);
					que.offer(new StringNum(tempStr, stringNum.num + 1));
				}
			}
		}
		return -1;
	}

	private static void swap(char[] arr, int i, int j) {
		char temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		
	}

}

//BFS即可，注意换位后要恢复原样，不然会影响之后的循环
//队列可以不用指针式，直接开成结构体型避免了malloc（）申请内存

#include <stdio.h>
#include <string.h>

#define MAXSIZE 200000  //注意自己写队列的时候要开足够大 有个十三位的数据 必须要
                        //用到二十万的队列 不然结果会是错的，通不过的可以看看是不
                        //队列爆了

typedef struct passWord{
    char str[13];
    int n;
    int cost;
}passWord;

int isPW(passWord pw){
    int n=pw.n;
    int i;
    for(i=0;i<n-3;i++){
        if(pw.str[i]=='2'&&pw.str[i+1]=='0'&&pw.str[i+2]=='1'&&pw.str[i+3]=='2') return 1;
    }
    return 0;
}

int BFS(passWord pw){
    passWord queue[MAXSIZE];
    int i;
    int front=0,end=0;
    queue[end]=pw;
    end=(end+1)%MAXSIZE;
    while(front!=end){
        passWord p=queue[front];
        front=(front+1)%MAXSIZE;
        if(isPW(p)){
            return p.cost;
        }else {
            for(i=0;i<p.n-1;i++){
                char temp = p.str[i];
                p.str[i]=p.str[i+1];
                p.str[i+1]=temp;
                p.cost++;
                queue[end]=p;
                end=(end+1)%MAXSIZE;
                temp = p.str[i];
                p.str[i]=p.str[i+1];
                p.str[i+1]=temp;
                p.cost--;

            }
        }
    }
    return -1;
}


int main(){
    passWord pw;
    int n;
    scanf("%d",&n);
    scanf("%s",pw.str);
    pw.n=n;
    pw.cost=0;
    printf("%d\n",BFS(pw));


    return 0;
}

}

#include<stdio.h>
#include<string>
#include<iostream>
#include<map>
#include<queue>
using namespace std;
bool check(string);
struct node{
	string v;
	int step;
	node(string x,int step):v(x),step(step){}
};
int main(){
	int N;
	string x;
	while(cin>>N){
		cin>>x;
		if(N<4){
			printf("-1\n");
			continue;
		}
		map<string,int> book;
		queue<node> Q;
		Q.push(node(x,0));
		int flag=0,step=-1;
		book[x]=1;
		while(!Q.empty()){
			node head=Q.front();Q.pop();
			if(check(head.v)){
				//flag=1;
				step=head.step;
				break;
			}
			string s=head.v;
			for(int i=0;i<=s.length()-2;i++){
				string tmp=s;
				tmp[i]=s[i+1];
				tmp[i+1]=s[i];
				if(book.count(tmp)==0){
					book[tmp]=1;
					Q.push(node(tmp,head.step+1));
				}
			}
		}
		printf("%d\n",step);
	}
}
bool check(string x){
	if(x.length()<4) return false;
	int i;
	for(i=0;i<=x.length()-4;i++)
		if(x[i]=='2'&&x[i+1]=='0'&&x[i+2]=='1'&&x[i+3]=='2')
			return true;
	return false;
}

#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct state
{
	string s;
	int t;
	state(string s,int t):s(s),t(t){}
};
queue<state> que;
void bfs(string s)
{
    state current(s,0);
	que.push(current);
	while(!que.empty())
	{
		state num=que.front();
		que.pop();
		if(num.s.find("2012")) 
		{
			cout<<num.t;
			return;
		} 
		else
		{
            for(int i=0 ; i<num.s.size()-1 ; i++)
            {
                state next(num.s,num.t+1);
                char c=next.s[i];
                next.s[i]=next.s[i+1];
                next.s[i+1]=c;
                que.push(next);
            }
			
		}
	}
    cout<<-1;
}
int main()
{
    string code;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<map>
using namespace std;
int num;
std::map<string, int> myMap;
void BFS(string str)
{
	queue<string> myQueue;
	myQueue.push(str);
	myMap[str] = 0;
	while (!myQueue.empty())
	{
		string temp = myQueue.front();
		myQueue.pop();
		if (temp.find("2012") != string::npos)
		{
			cout << myMap.find(temp)->second << endl;
			return;
		}	
		for (int i = 0; i < temp.size() - 1; i++)
		{
			string temp1 = temp;
			char c = temp1[i];
			temp1[i] = temp1[i + 1];
			temp1[i + 1] = c;
			if (myMap.find(temp1) == myMap.end())
			{
				myQueue.push(temp1);
				myMap[temp1] = myMap.find(temp)->second+1;
			}
		}
	}
	cout << -1 << endl;
}
int main()
{
	string str;
    int n;
	while (cin >> n >> str)
	{
		num = 0;
		myMap.clear();
		BFS(str);
	}
	return 0;
}

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
/*算法:N叉树层次遍历(BFS)*/
int main()
{
	int N;
	string str;
	queue<string> Q;//BFS队列
	unordered_map<string, bool> mark;//访问过标记，用哈希查询比较快
	while (cin>>N>>str)
	{
		Q.push(str);
		mark[str] = true;
		//l_c:当前层最后一个 l_n:下一层最后一个 current:当前字符串
		string l_c = str, l_n = "", current = str;
		int count = 0;//次数
		//只有当缺0||1||2时才无法解密
		if (str.find('0') == str.npos 
			|| str.find('1') == str.npos 
			|| str.find('2') == str.npos)
			count = -1;
		else
		{
			while (str.find("2012") == str.npos)
			{
				for (unsigned int i = 0; i < N - 1; i++)
				{
					str = current;
					swap(str[i], str[i + 1]);//往右交换相邻字符
					if (mark[str] == false)//没访问过的入队
					{
						Q.push(str);
						mark[str] = true;
						l_n = str;
					}
					else
						continue;
				}
				if (current == l_c)//到达当前层最后一个，就要加一层
				{
					l_c = l_n;
					count++;
				}
				Q.pop();
				str = Q.front();
				current = str;
			}		
		}
		cout << count << endl;
		//多组输入善后
		while (!Q.empty())
				Q.pop();
			mark.clear();
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

/*
	有连续 2012 -> s.find("2012") != string::npos
	相邻的字符移位 -> swap(s[i-1], s[i])
	统计移位次数 -> map<string, int>
	注意的点：对于2222这样的字符串，其移位后可能会存在相同的字串，要去重 
*/

map<string, int> M;		//M[s] 表示字符串 s 的已移位次数
int BFS(string s) {
	queue<string> Q;
	Q.push(s);
	M[s] = 0;	
	while(!Q.empty()) {
		string current = Q.front();
		if(current.find("2012") != string::npos) {	//若找到，返回移位次数 
			return M[current];
		}
		Q.pop();
		for(int i = 1; i < current.size(); i++) {	//遍历分支 
			string next = current;
			swap(next[i - 1], next[i]);
			if(M.find(next) == M.end()) {	//如果移位后的新字符串还没出现过 
				M[next] = M[current] + 1;	//**则它的移位次数是它父亲的次数+1** 
				Q.push(next);				
			} 
			else {							//若已经出现过，抛弃 
				continue;
			}
		}
	}
	
	return -1;	//无法组成，返回-1 
}

int main() {
	int n;
	string s;
	while(cin >> n >> s) {
		cout << BFS(s) << endl;
	}
}

#include<bits/stdc++.h>

using namespace std;


struct Status
{
    string x;
    int t;
    Status(string x1,int t1):x(x1),t(t1) {}
};

string change(string x,int n)
{
    char ch;
    if(n<x.size()-1)
    {
        ch=x[n];
        x[n]=x[n+1];
        x[n+1]=ch;
    }
     return x;  
}

void BFS(string x)
{
   queue<Status>myqueue;
   Status begin(x,0);
   myqueue.push(begin);
   while(!myqueue.empty())
   {
       Status current=myqueue.front();
       myqueue.pop();
       if(current.x.find("2012")!=x.npos)//如果2012在开头那么返回0 得想办法处理
       {
           cout<<current.t;
           break;//找到，那么输出，函数结束
       }
       
       current.t=current.t+1;
       string x=current.x; //必须先记录下来再去循环，否则循环里面不能实现本意
       for(int i=0;i<x.size()-1;i++)//进行广度优先遍历
       {
           current.x=change(x,i);
           myqueue.push(current);
       }
       
   }
}


int main()
{
    int n;
    cin>>n;
    string x;
    while(cin>>x)
        BFS(x);
    return 0;
}

//BFS算法
#include <iostream>
(720)#include <algorithm>
#include <map>
(747)#include <queue>
#include <set>

using namespace std;

set<string> str_set;
queue<string> str_queue;

bool in_str(string str)									//判断2012是否在串中
{
	for (int i = 0; i < str.length() - 4; i++)
	{
		if (str.substr(i, 4) == "2012")
			return true;
	}
	return false;
}

string swap_str(string str, int i, int j)				//交换串中i，j位置的值
{
	char temp = str[i];
	str[i] = str[j];
	str[j] = temp;
	return str;
}

int get_times(string str)
{
	int cnt = 0, index = 0;
	if (in_str(str))
		return index;
	else
	{
		str_queue.push(str);
		str_set.insert(str);
	}
	
	bool tag = true;

	while (!str_queue.empty() && tag)
	{
		//cout << "队列长度为：" << str_queue.size() << endl;
		int qu_length = str_queue.size();
		for (int i = 0; i < qu_length; i++)
		{
			string s = str_queue.front();
			str_queue.pop();
			if (in_str(s))
			{
				tag = false;
				index = cnt;
				break;
			}
			for (int j = 0; j < s.length() - 1; j++)
			{
				string swapped_s = swap_str(s, j, j + 1);
				if (str_set.find(swapped_s) == str_set.end())
				{
					str_queue.push(swapped_s);
					str_set.insert(swapped_s);
				}
			}
		}
		cnt++;
	}
	return index;
}

int main()
{
	int n;
	string str;
	while ( cin >> n >> str)
	{
		int valid[3] = { 0 };
		for (auto c : str)
			valid[c - '0']++;
		if (valid[0] >= 1 && valid[1] >= 1 && valid[2] >= 2)
		{
			cout << get_times(str) << endl;
		}
		else
			cout << -1 << endl;
	}
}

#include <bits/stdc++.h>
using namespace std;

struct Code{
    string s;                                            //记录当前的字符串
    int m;                                               //记录当前移位的次数
    Code(string s, int m): s(s), m(m) {}
};

string swap(string nstr, int k){
    char tmp;
    tmp = nstr[k];
    nstr[k] = nstr[k+1];
    nstr[k+1] = tmp;
    return nstr;
}

map<string, bool> visit;                        //用一个 map 记录当前的字符串是否在之前出现过

void BFS(string st){
    queue<Code> Q;
    Q.push(Code(st, 0));                      //压入初始状态，此时结构体中的m = 0(移位 0 次)
    int len = st.size();
    visit[st] = true;
    while(!Q.empty()){
        Code current = Q.front();                              //定义一个结构体 current 表示当前的状态
        Q.pop();
        if(current.s.find("2012") != string::npos){               //当前状态符合题意，也就是找到了
            cout << current.m << endl;                      //输出 current 结构体中的 m，也就是移位的次数
            visit.clear();                   //多次输入一定要 clear，不然会影响下一次输入的结果
            return;
        }
        string str;
        for(int i = 0; i < len - 1; ++i){      //由题意知最多输入13个字符，那最多就有12种移位方式
            Code next(current.s, current.m + 1);   //定义一个结构体next表示当前状态的下一状态，注意区别就是移位次数 +1 了
            if(i == 0){
                str = swap(next.s, 0);
            }
             else if(i == 1){
                str = swap(next.s, 1);
            }
             else if(i == 2){
                str = swap(next.s, 2);
            }
             else if(i == 3){
                str = swap(next.s, 3);
            }
             else if(i == 4){
                str = swap(next.s, 4);
            }
             else if(i == 5){
                str = swap(next.s, 5);
            }
             else if(i == 6){
                str = swap(next.s, 6);
            }
             else if(i == 7){
                str = swap(next.s, 7);
            }
             else if(i == 8){
                str = swap(next.s, 8);
            }
             else if(i == 9){
                str = swap(next.s, 9);
            }
             else if(i == 10){
                str = swap(next.s, 10);
            }
             else if(i == 11){
                str = swap(next.s, 11);
            }
            next.s = str;
            if(visit[next.s] == true){            //判断当前的字符串是否出现过
                continue;                     //出现过就不把当前字符串压入队列(无效状态)
            }
            Q.push(next);                         //没出现过把新的字符串压入队列(新的有效状态)
            visit[next.s] = true;                //新的字符串现在出现过了，map 中设为 true
        }
    }
    visit.clear();                          //多次输入一定一定要 clear，不然下面的输入输出结果永远是 -1
    cout << "-1" << endl;                   //所有有效状态遍历完了，还是没有合格的，输出 -1
}

int main(){
    int n;
    string str;
    while(cin >> n){
        cin >> str;
        BFS(str);                           //人生的第一个BFS，通过的瞬间好爽
    }
    return 0;
}

满满的成就感，没看过评论区，从一开始尝试递归（发现走不通）到仅靠bfs（发现空间复杂度太大），再经过不断的优化，自己实现了bfs+map，然后再看评论区，发现英雄所见略同，太爽了！！收获：以后遇到不会的，多想多尝试，否则很容易养成一种 一不会就看解题报告 的陋习，大家加油~

#include <bits/stdc++.h>
(755)#include <queue>
using namespace std;
int n;
map<string,bool>m;
typedef struct {
	string s;
	int depth;
} tree;

bool isTrue(tree str) {

		for(int i=0; i<=n-4; i++) {
			if(str.s.substr(i,4)=="2012") {
				return true;
			}
		}
		return false;

}
string ownswap(tree str,int x,int y ) {
	char tmp=str.s[x];
	str.s[x]=str.s[y];
	str.s[y]=tmp;
	return str.s;
}
int main() {
	queue<tree>q;

	//int flag=0;
	tree str,tmp;
	cin>>n>>str.s;
	str.depth=0;
	m[str.s]==true;
	q.push(str);
	while(!q.empty()) {
		tmp=q.front();
		if(isTrue(tmp)) {
			cout<<tmp.depth<<endl;
			break;
		}
		//flag++;
		q.pop();
		for(int i=0; i<n-1; i++) {
			tree tmp1;
			tmp1.s=ownswap(tmp,i,i+1);
			tmp1.depth=tmp.depth+1;
			if(m[tmp1.s]==true) continue;
			else{
				m[tmp1.s]=true;
				q.push(tmp1);
			}
			
			
		}

	}
	return 0;
}

#include<iostream>
(720)#include<cstdio>
#include<map>
(747)#include<cstring>
#include<queue>
using namespace std;
map<string,int> visit;
int BFS(int n,string s){
    queue<string>    Q;
    Q.push(s);
    visit[s]=1;
    while(!Q.empty()){
        string temp=Q.front();
        Q.pop();
        if(temp.find("2012",0)!=string::npos)
            return visit[temp]-1;
        for(int i=0;i<n-1;i++){
            string str=temp;
            swap(str[i],str[i+1]);
            if(visit[str]!=0)    continue;
            else{
                Q.push(str);
                visit[str]=visit[temp]+1;
            }
        }
    }
    return -1;
}
int main(){
    int N;
    string input;
    while(scanf("%d",&N)!=EOF){
        cin>>input;
        printf("%d\n",BFS(N,input));
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
struct code{
	string code_str;
	int step;
};
int getStep(string str,int n){
	vector<code> vi;
	int index=0; //step代表当前字符串是交换了几次的结果，初始值为0，因为可能存在一开始就有2012 
	code c;
	c.step=0;
	c.code_str=str;
	vi.push_back(c); //初始化 
	//开始只想到了全排列，所以跳出的条件是 pow(3,n) 比如 长度为4的串，最多有 3的四次方个排列 .
	//看完讨论后才知道是BFS，哈哈 ，用队列比较好 
	while(vi.size()<pow(3,n)){ 
		if(vi[index].code_str.find("2012")!=-1){
			return vi[index].step;
		}else{
			string tem;
			tem=vi[index].code_str;
			for(int i=0;i<n-1;i++){ //没找到 那么只能由当前的字符串交换一次后所有结果加进去，在加的时候顺便判读一下是否有了 2012 
				swap(tem[i],tem[i+1]);
				code next;
				next.code_str=tem;
				next.step=vi[index].step+1;
				if(tem.find("2012")!=-1){ // 在加的时候顺便判读一下是否有了 2012 
					return next.step;
				}
				vi.push_back(next);
				tem=vi[index].code_str;
			}
			index++;
		}
	}
	return -1;
}
int main(){
	int n;
	string str;
	
	while(cin>>n>>str){
		if(n<4){
			cout<<-1<<endl;
		}else{
			cout<<getStep(str,n)<<endl;
		}
	}
	return 0;
}

/*
    考察BFS 
*/
#include <bits/stdc++.h>
using namespace std;
map<string,int> visit; // 标记数组，并且还能还能表示交换次数
string swap(string str,int x,int y){ // 交换字符串x,y位置的字符
	char temp = str[x];
	str[x] = str[y];
	str[y] = temp;
	return str;	
} 
int BFS(string str){
	visit.clear(); // 每次标记数组都要清0
	queue<string> myQueue;
	myQueue.push(str);
	visit[str] = 0; // 第一次进来交换次数为0
	while(!myQueue.empty()){ // 队列非空时才进行
		string cur = myQueue.front();
		myQueue.pop();
		if(cur.find("2012")!=string::npos){ // 如果当前直接就找到了，那么直接返回
			return visit[cur];
		}else{
			for(int i = 0;i<cur.size()-1;i++){
				string temp = swap(cur,i,i+1);
				if(visit.find(temp)==visit.end()){ // 如果不在标记中，即之前没有出现过，才入队
					myQueue.push(temp);
					visit[temp] = visit[cur]+1; // 交换次数是上一层的次数+1
				}
			}
		}
	}
	return -1; // 走完所有可能都没有找到，返回-1
}

int main(){
	int n; // n的意义不明
	string str;
	while(cin>>n>>str){
		cout<<BFS(str)<<endl;
	}
	return 0;
}