蓝桥杯17省赛 C9 青蛙跳(bfs)

蓝桥杯17省赛 C9 青蛙跳(bfs)

标题：青蛙跳杯子

X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。

WWWBBB

其中，W字母表示白色青蛙，B表示黑色青蛙，*表示空杯子。

X星的青蛙很有些癖好，它们只做3个动作之一：
1. 跳到相邻的空杯子里。
2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。

对于上图的局面，只要1步，就可跳成下图局面：

WWW*BBB

本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。

输入为2行，2个串，表示初始局面和目标局面。
输出要求为一个整数，表示至少需要多少步的青蛙跳。

例如：
输入：
WWBB
WWBB

则程序应该输出：
2

再例如，
输入：
WWWBBB
BBBWWW

则程序应该输出：
10

我们约定，输入的串的长度不超过15

---

笨笨有话说：
我梦见自己是一棵大树，
青蛙跳跃，
我就发出新的枝条，
春风拂动那第 5 层的新枝,
哦，我已是枝繁叶茂。

=======================

思路:
最短路径->bfs
记录每一次状态,若出现已经有过的状态则否决后面出现这个状态的路线->HashMap
遍历交换情况的时候,做完对交换后出现的状态的记录/判断后,回滚到之前的状态,保持下一次交换的时候步数一致->回溯

心得:
这题目很迷就,也不说清楚,到底是不是只有一个空杯

public class 青蛙跳_bfs_9 {
	static String s;
	static Queue<String> que =new LinkedList<String>();	//感觉还是饿汉式爽
	static Map<String ,Integer> map =new HashMap<String, Integer>();
	public static void main(String[] args) {
		init();

		int lev =0;
		String tmp ="";
		char[] c =null;
		while(true) {
			tmp =que.poll();
			lev =map.get(tmp);
			c =tmp.toCharArray();
			for(int i =0 ;i <c.length ;i ++) {
				if(c[i] =='*') continue; 
				for(int j =-3 ;j <=3 ;j ++) {
					if(i +j<0 ||i +j >=c.length ||j ==0 ||c[i +j] !='*') continue;
					
					swap(c ,i ,i +j);	//数组传递的是地址所以不需要写返回值
					tmp =String.valueOf(c);
					if(tmp.equals(s)) { System.out.println(lev +1); return ;}
					if(!map.containsKey(tmp)) { que.add(tmp); map.put(tmp, lev +1);}
					swap(c ,i ,i +j);
				}
			}
		}
	}
	private static void swap(char[] c, int i, int j) {
		c[i] ^=c[j];
		c[j] ^=c[i];
		c[i] ^=c[j];
	}
	private static void init() {
		Scanner sc = new Scanner(System.in);
		String sta =sc.next();
		s =sc.next();
		sc.close();
		que.add(sta);
		map.put(sta, 0);
	}
}