欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-14 07:52:05
...

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

标题:青蛙跳杯子

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

WWWBBB

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

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

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

WWW*BBB

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

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

例如:
输入:
WWBB
WWBB

则程序应该输出:
2

再例如,
输入:
WWWBBB
BBB
WWW

则程序应该输出:
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);
	}
}
相关标签: 蓝桥