Submission #68234

---

Source Code Expand

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;

public class Main {

	static final int firstN = 0, lastN = 1;
	public static void main(String[] args) {
		doIt();
	}

	static void doIt(){
		Scanner sc = new Scanner(System.in);
		String first = sc.next();
		String last = sc.next();
		int n = sc.nextInt();
		String[] ary = new String[n + 2];
		ary[firstN] = first;
		ary[lastN] = last;
		int[][] diff = new int[n + 2][n + 2];
		int[] back = new int[n + 2];
		boolean bOK = false;
		for(int i = 2; i < n + 2; i++) ary[i] = sc.next();
		if(first.equals(last)){
			System.out.println(0);
			System.out.println(first);
			System.out.println(last);
			return;
		}
		for(int i = 0; i < n + 2; i++){
			for(int j = i; j < n + 2; j++) diff[i][j] = diff[j][i] = dif(ary[i], ary[j]);
		}
		HashSet<Integer> hash = new HashSet<Integer>();
		LinkedList<Integer> queue = new LinkedList<Integer>();
		queue.add(firstN);
		hash.add(firstN);
		back[firstN] = -1;
		int c = 0;
		while(!queue.isEmpty()){
			if(n < c) break;
			int s = queue.size();
			for(int i = 0; i < s; i++){
				int ti = queue.poll();
				for(int j = 0; j < n + 2; j++){
					if(diff[ti][j] == 1){
						if(!hash.contains(j)){
							queue.add(j);
							back[j] = ti;
							hash.add(j);
						}
						if(diff[j][lastN] == 1){bOK = true;break;}
					}
				}
			}
			c++;
		}
		if(bOK){
			Stack<Integer> stack = new Stack<Integer>();
			int t = lastN;
			while(t != -1){
				stack.push(t);
				t = back[t];
			}
			System.out.println(stack.size() - 2);
			while(!stack.isEmpty()) System.out.println(ary[stack.pop()]);
		}
		else System.out.println(-1);
	}
	static int dif(String s1, String s2){
		int ret = 0;
		for(int i = 0; i < s1.length(); i++) if(s1.charAt(i) != s2.charAt(i)) ret++;
		return ret;
	}

}

Submission Info

Judge Result