1878: 蓝桥杯2017年第八届真题-青蛙跳杯子（JAVA题解 BFS）

解题思路:

bfs, 我以青蛙位置做bfs，也可以以空杯子位置做bfs
注意事项:

参考代码:

import java.io.*;
import java.util.*;

// https://www.dotcpp.com/oj/problem1878.html
// bfs, 我以青蛙位置做bfs，也可以以空杯子位置做bfs
public class Main {
	static class Frog{
		char c;
		int count;  // 计数
		int index;  // 字符串下标
		String path = "";
		Frog(char c, int index, int count, String path){
			this.c = c;
			this.count = count;
			this.index = index;
			this.path = path;
		}
		
	}
	static BufferedReader cin;
	static PrintWriter out;
	static String start;
	static String end;
	static HashSet<String> map;
	static int n;
	public static void main(String[] args) throws IOException{
		cin = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(new OutputStreamWriter(System.out));
		map = new HashSet<>();
		start = cin.readLine();
		end = cin.readLine();
		n = start.length()-1;
		Queue<Frog> que = new LinkedList<>();
		for(int i = 0; i < start.length(); i++){  // 寻找初始节点
			if(start.charAt(i) == 'W'  || start.charAt(i) == 'B') {  // 是青蛙
				que.add(new Frog(start.charAt(i), i, 0, start));
			}
		}
		map.add(start);
		Frog t = null;
		while(!que.isEmpty()) {
			t = que.poll();
			start = t.path;
			if(start.equals(end))
				break;
			int index = t.index;
			int count = t.count;
			char c = t.c;
			if(index > 0 && start.charAt(index-1)=='*') {  // 青蛙向左跳一格
				StringBuilder nextS = new StringBuilder(start);
				nextS.setCharAt(index-1, c);
				nextS.setCharAt(index, '*');
				String s = nextS.toString();
				if(!map.contains(s)) {
					map.add(s);
					for(int i = 0; i < start.length(); i++){  // 寻找节点
						if(start.charAt(i) == 'W'  || start.charAt(i) == 'B') 
							que.add(new Frog(start.charAt(i), i, count+1, s));
					}
				}
				
			}
			if(index > 1 && start.charAt(index-2)=='*') {  // 青蛙向左跳两格
				StringBuilder nextS = new StringBuilder(start);
				nextS.setCharAt(index-2, c);
				nextS.setCharAt(index, '*');
				String s = nextS.toString();
				if(!map.contains(s)) {
					map.add(s);
					for(int i = 0; i < start.length(); i++){  // 寻找节点
						if(start.charAt(i) == 'W'  || start.charAt(i) == 'B')
							que.add(new Frog(start.charAt(i), i, count+1, s));
					}
				}
			}
			if(index > 2 && start.charAt(index-3)=='*') {  // 青蛙向左跳三格
				StringBuilder nextS = new StringBuilder(start);
				nextS.setCharAt(index-3, c);
				nextS.setCharAt(index, '*');
				String s = nextS.toString();
				if(!map.contains(s)) {
					map.add(s);
					for(int i = 0; i < start.length(); i++){  // 寻找节点
						if(start.charAt(i) == 'W'  || start.charAt(i) == 'B') 
							que.add(new Frog(start.charAt(i), i, count+1, s));
					}
				}
			}
			if(index < n && start.charAt(index+1)=='*') {  // 青蛙向右跳一格
				StringBuilder nextS = new StringBuilder(start);
				nextS.setCharAt(index+1, c);
				nextS.setCharAt(index, '*');
				String s = nextS.toString();
				if(!map.contains(s)) {
					map.add(s);
					for(int i = 0; i < start.length(); i++){  // 寻找节点
						if(start.charAt(i) == 'W'  || start.charAt(i) == 'B')  
							que.add(new Frog(start.charAt(i), i, count+1, s));
					}
				}
			}
			if(index < n-1 && start.charAt(index+2)=='*') {  // 青蛙向右跳两格
				StringBuilder nextS = new StringBuilder(start);
				nextS.setCharAt(index+2, c);
				nextS.setCharAt(index, '*');
				String s = nextS.toString();
				if(!map.contains(s)) {
					map.add(s);
					for(int i = 0; i < start.length(); i++){  // 寻找节点
						if(start.charAt(i) == 'W'  || start.charAt(i) == 'B')  
							que.add(new Frog(start.charAt(i), i, count+1, s));
					}	
				}
				
			}
			if(index < n-2 && start.charAt(index+3)=='*') {  // 青蛙向右跳两格
				StringBuilder nextS = new StringBuilder(start);
				nextS.setCharAt(index+3, c);
				nextS.setCharAt(index, '*');
				String s = nextS.toString();
				if(!map.contains(s)) {
					map.add(s);
					for(int i = 0; i < start.length(); i++){  // 寻找节点
						if(start.charAt(i) == 'W'  || start.charAt(i) == 'B')
							que.add(new Frog(start.charAt(i), i, count+1, s));
					}	
				}
				
			}
			
		}
		out.println(t.count);
		out.flush();
		out.close();
		

	}
	

}