题意：输入一个长度为n（2<=n<=13)的字符串（所有字符为‘0’，‘1’或‘2’），通过交换相邻的两个字符，至少要交换多少次才能处出现字串“2012”，输出这个值，若不能则输出-1。

输入：

5

02120

输出

1

思路：bfs搜索，每个串代表一个状态,最多有3^13个状态。每一个字符串可以转换成对应的三进制数，用来标记该串是否访问过。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

struct node{

	char str[15];

	int cnt;

};

bool vis[1600000],get;

char str[15];

int n;

queue<struct node> Q;

int get_num(char temp[]){

	int i,num = 0;

	for(i=n-1; i>=0; i--){

	    num *= 3;

	    num += temp[i] - '0';

	}

	return num;

}

bool judge(char temp[]){

	char sub[5];

	int i;

	for(i=0; i<=n-4; i++)

	    if(temp[i] == '2' && temp[i+1] == '0' && temp[i+2] == '1' && temp[i+3] == '2')

	        return true;

	return false;

}

int bfs(){

	for(int i=0; i<1600000; i++)

		vis[i] = false;

	while(!Q.empty())

		Q.pop();

	node sta,sta1,sta2;

	for(int i=0; i<n; i++)

	    sta.str[i] = str[i];

	sta.cnt = 0;

	Q.push(sta);

	while(!Q.empty()){

		sta1 = Q.front();

		Q.pop();

		int num1 = get_num(sta1.str);

		if(judge(sta1.str))

			return sta1.cnt;

		vis[num1] = true;

		for(int i=0; i<n-1; i++){

			sta2 = sta1;

			sta2.cnt ++;

			char ch = sta2.str[i];

			sta2.str[i] = sta2.str[i+1];

			sta2.str[i+1] = ch;

			int num2 = get_num(sta2.str);

			if(!vis[num2])

				Q.push(sta2);

		}

	}

}

int main(){

    int i,j,cnt[10];

	while(cin >> n){

		cin >> str;

        cnt[0] = cnt[1] = cnt[2] = 0;

		for(i=0; i<n; i++)

		    cnt[str[i] - '0'] ++;

		if(cnt[0] == 0 || cnt[1] == 0 || cnt[2] < 2){

			cout << -1 << endl;

			continue;

		}

		int ans = bfs();

		cout << ans << endl;

	}

	return 0;

}