PKU 2138-Travel Games

2138 -- Travel Games

問題概要

牛さんが "travel games"というゲームをして遊ぶことにした．
"travel games"はある牛が作った単語に一文字足して次の単語を作るということを繰り返していくゲームだ．
さて辞書が与えられた時に最も最終結果の単語がながくなるようなゲームも仕方を求め，最終結果の単語を出力せよ

解法

幅優先探索する

実装(Java)

import java.util.*;
import java.math.*;
import java.io.*;
import java.util.regex.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.lang.System.*;

public class Main {
	Scanner cin;
	Boolean solve(String a,String b){
		int matched=0;
		if(a.length()!=b.length()+1)return false;
		for(int i=0;i<a.length();i++){
			if(a.charAt(i)==b.charAt(matched)){
				matched++;
				if(matched==b.length())return true;
			}
		}
		return false;
	}
	void run(){
		cin=new Scanner(System.in);
		int D=cin.nextInt();
		D+=1;
		int [][]G=new int[D][D];
		String[] in=new String[D];
		String base=cin.next();
		for(int i=0;i<D-1;i++){
			in[i]=cin.next();
		}
		in[D-1]=base;
		for(int i=0;i<D;i++){
			for(int j=0;j<D;j++){
				G[j][i]=(solve(in[i],in[j])?1:0);
			}
		}
		Queue<Integer> que=new LinkedList<Integer>();
		que.add(D-1);
		Boolean[] ac=new Boolean[D];
		int ans=0;
		while(que.size()!=0){
			int now=que.poll();
			ac[now]=true;
			for(int i=0;i<D;i++){
				if(G[now][i]==1){
					que.add(i);
				}
			}
			ans=now;
		}

		printf("%s\n",in[ans]);
	}

	void printf(String format,Object... args){
		System.out.printf(format, args);
	}

	public static void main(String[] args) {
		new Main().run();
	}

}