密码锁

描述

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

输入

第一行输入N，第二行输入N个数字，只包含0，1，2

输出

样例输入1

5

02120

7

2122121

样例输出1

1
-1

import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;  
  
public class Main  {
	
	static class Node {  //队列节点
		String s;
		int step;
		Node(String s, int step){
			this.s = s;
			this.step = step;
		}
	}
	
	public static String swap(String s, int index) {  //相邻交换方法
		char[] charstr = s.toCharArray();
		char tmpc = charstr[index];
		charstr[index] = charstr[index+1];
		charstr[index+1] = tmpc;
		return new String(charstr);
	}
        public static void main(String args[]){  
    	Scanner input = new Scanner(System.in);
    	while (input.hasNext()) {
	        int n = input.nextInt();
	        Node p = new Node(input.next(), 0);
	        int[] count = new int[3];
	        for (int i = 0; i < n; i++)
	        	count[p.s.charAt(i)-'0']++;
	        if (count[0] < 1 || count[1] < 1 || count[2] < 2) {   
	        	System.out.println(-1);
	        	continue;
	        }
	        List<String> record = new ArrayList<>();    //标记已进队密码
	        Queue<Node> queue = new LinkedList<Node>();  //队列
	        queue.offer(p);
	        record.add(p.s);
	        // bfs 
	        while (!queue.isEmpty()) {
	        	Node first = queue.poll();     //出队
	        	if (first.s.contains("2012")) { 
	        		System.out.println(first.step);
	        		break;
	        	}
	        	for (int i = 0; i < n - 1; i++) {
	        		String tmps = new String(swap(first.s, i));
	        		if (record.contains(tmps))       //已存在不进队
	        			continue;
	        		queue.offer(new Node(tmps, first.step+1));
	        		record.add(tmps);
	        	}
	        }
    	}
    }  
}