首页 > 试题广场 >

密码锁

[编程题]密码锁

热度指数：4262 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

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

输出描述:

输出字符串要移几位才能解开密码，如果无论移位多少次都解不开密码，输出-1

示例1

输入

输出

1
1

算法知识视频讲解

Java

牛客332198386号

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            //移位
        	int n=sc.nextInt();
        	String code=sc.next();
        	int moveTime=getMoveTime(code);
        	System.out.println(moveTime);
        	
        }
    }

	private static int getMoveTime(String code) {
		if(code.length()<4)return -1;
		List<String>record=new ArrayList<>();//记录已经交换过的结果，剪枝。
		Queue<Help>queue=new LinkedList<>();
		Help help=new Help(code,0);
		queue.offer(help);
		record.add(code);
		while(!queue.isEmpty()) {
			help=queue.poll();
			if(help.s.contains("2012"))
				return help.cnt;
			for(int i=0;i<code.length()-1;i++) {
				char[]arr=help.s.toCharArray();
				char temp = arr[i];
		        arr[i] = arr[i+1];
		        arr[i+1] = temp;
		        String after=new String(arr);
		        if(!record.contains(after)) {
		        	record.add(after);
		        	queue.offer(new Help(after,help.cnt+1));
		        }
			}
		}
		return -1;
	}
}
class Help{
	String s;
	int cnt;
	Help(String s,int cnt){
		this.s=s;
		this.cnt=cnt;//交换次数
}

发表于 2020-04-07 14:55:49 回复(0)