AOJ0140 Bus Line

問題リンク Bus Line

• 解法

基本方針は幅優先探索による最短路探しです。が、思った以上に面倒な問題です。
遷移先を見極める必要があります。
6-9においては1方向に進むので問題ありません。
0-5の区間は今どちら向きに進んでいるかの向きの情報が必要になります。この向きは0になると反転します。
なので、単なるバス停番号でなく、どちら向きなのかという拡張した頂点における幅優先探索です。
更にこの問題は最短移動経路を出す必要があるので、新しい頂点にたどり着くと同時に経路の文字列を作成しています。

• ソース

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//Bus Line
public class AOJ0140 {

	static class T{
		int p;
		boolean up;
		String s;
		public T(int p, String s, boolean d) {
			this.p = p;
			this.up = d;
			this.s = s;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while(t--!=0){
			int s = sc.nextInt();
			int g = sc.nextInt();
			List<T> l = new ArrayList<T>();
			l.add(new T(s,s+"",true));
			l.add(new T(s,s+"",false));
			boolean[][] u = new boolean[10][2];
			u[s][0] = u[s][1] = true;
			while(!l.isEmpty()){
				List<T> next = new ArrayList<T>();
				for(T w:l){
					if(w.p==g){
						next.clear();
						System.out.println(w.s);
						break;
					}
					if(w.up){
						if(w.p==9){
							if(!u[5][1]){
								u[5][1] = true;
								next.add(new T(5,w.s+" "+5,false));
							}
						}
						else if(!u[w.p+1][0]){
							u[w.p+1][0] = true;
							next.add(new T(w.p+1, w.s+" "+(w.p+1),true));
						}
					}
					else{
						if(w.p==0){
							if(!u[1][0]){
								u[1][0] = true;
								next.add(new T(1,w.s+" 1",true));
							}
						}
						else{
							if(w.p>=6)continue;
							if(!u[w.p-1][1]){
								u[w.p-1][1] = true;
								next.add(new T(w.p-1,w.s+" "+(w.p-1),false));
							}
						}
					}
				}
				l = next;
			}
		}
	}
}