蓝桥杯2017年第八届真题-青蛙跳杯子 （Java代码）

解题思路:

注意事项:

参考代码:

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;
public class Main {
	public static String s1, s2;
	public static int ans;
	public static Map<String ,Integer> mp = new HashMap<>();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		s1 = sc.next();
		s2 = sc.next();
		BFS();
	}
	public static void BFS(){
		int [] dir = {-3, -2, -1, 1, 2, 3};
		LinkedList<Node> ll = new LinkedList<>();
		ll.addLast(new Node(s1, 0));
		while(!ll.isEmpty()){
			Node t = ll.getFirst();
			ll.removeFirst();
			if(t.s.equals(s2)){
				System.out.println(t.step);
				return ;
			}
			int k = t.s.length();
			for(int i = 0; i < k; i++){
				for(int j = 0; j < 6; j++){
					int n = i + dir[j];
					String tmp = t.s;
					if(n>=0&&n<k&&tmp.charAt(n)=='*'){
						StringBuffer sb = new StringBuffer(tmp);
						char c = sb.charAt(n);
						sb.setCharAt(n, sb.charAt(i));
						sb.setCharAt(i, c);
						tmp = sb.toString();
						
						if(mp.get(tmp) == null){
							mp.put(tmp, 1);
							ll.addLast(new Node(tmp, t.step+1));
						}
					}
				}
			}
		}
		return ;
	}
}
class Node{
	String s;
	int step;
	public Node(String s, int step){
		this.s = s;
		this.step = step;
	}
}