【藍橋杯省賽真題】青蛙跳杯子（bfs）

問題描述

樣例輸入

*WWBB
WWBB*
           

樣例輸出

樣例輸入

WWW*BBB
BBB*WWW
           

樣例輸出

參考代碼

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
//自定義類
class State{
	String string;
	int pos;
	int step;
	public State(String string,int pos,int step) {
		this.pos=pos;
		this.step=step;
		this.string=string;
	}
}

public class Main {
    static int []arr= {1,2,3,-3,-2,-1};
    static String str1;
    static String str2;
    static Queue<State> queue;
    static Set<String>set=new HashSet<>();
    
    public static void main(String[] args) {
    	Scanner sc=new Scanner(System.in);
    	str1=sc.nextLine();
    	str2=sc.nextLine();
    	queue=new LinkedList<State>();
    	int pos=0;
    	for (int i = 0; i < str1.length(); i++) {
			if (str1.charAt(i)=='*') {
				pos=i;
				break;
			}
		}
 
    	System.out.println(bfs(str1,pos,0));
    	sc.close();
    }
    
    
	private static int bfs(String now, int x, int step) {
		queue.add(new State(now, x, step));
		while(!queue.isEmpty()) {
			State nowState=queue.poll();
			//
			if (nowState.string.equals(str2)) {
				return nowState.step; 
			}
			//去重
			if (set.contains(nowState.string)) {
				continue;
			}else {
				set.add(nowState.string);
			}
			for (int i = 0; i < arr.length; i++) {
				int nextx=nowState.pos+arr[i];
				if (nextx<nowState.string.length()&&nextx>=0) {
					String temp=nowState.string;
					String nextPatten=swap(nowState.pos,nextx,temp);
					State nextState =new State(nextPatten,nextx,nowState.step+1);
					if (!set.contains(nextPatten)) {
						queue.add(nextState);
					}
				}
			}
		
		}
		return -1;
		
	}


	private static String swap(int a, int b, String str) {
		char cs[] = str.toCharArray();
		char temp = cs[a];
		cs[a] = cs[b];
		cs[b] = temp;
		str = new String(cs);
		return str;		
	}

    
}