UVA – 429 – Word Transformation

iimport java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(in.readLine());
		String s = in.readLine();
		while (T-- != 0) {
			
			ArrayList<String> items = new ArrayList<String>();
			while (!(s = in.readLine()).equals("*"))
				items.add(s);

			HashMap<String, List<String>> graph = generateGraph(items);

			while ((s = in.readLine()) != null && !(s).equals("")) {
				String[] tokens = s.split(" ");
				String source = tokens[0];
				String distination = tokens[1];
				Integer length = BFS(source, distination, graph);

				System.out.println(source + " " + distination + " " + length);
			}
			if(T!=0)
				System.out.println();
		}
	}

	public static HashMap<String, List<String>> generateGraph(ArrayList<String> words) {
		HashMap<String, List<String>> g = new HashMap<String, List<String>>();
		for (int i = 0; i < words.size(); i++) {
			List<String> adj = new LinkedList<String>();
			for (int j = 0; j < words.size(); j++) {
				if (i == j)
					continue;
				if (linked(words.get(i), words.get(j))) {
					adj.add(words.get(j));
				}
			}

			g.put(words.get(i), adj);
		}

		return g;
	}

	public static boolean linked(String a, String b) {
		if (a.length() != b.length())
			return false;

		int difference = 0;
		for (int i = 0; i < a.length(); i++)
			difference += a.charAt(i) != b.charAt(i) ? 1 : 0;

		return difference == 1;
	}

	public static Integer BFS(String source, String distination, HashMap<String, List<String>> g) {

		HashMap<String, Integer> distance = new HashMap<String, Integer>();
		HashMap<String, Boolean> visited = new HashMap<String, Boolean>();

		for (String s : g.keySet()) {
			distance.put(s, -1);
			visited.put(s, false);
		}

		Queue<String> que = new LinkedList<String>();
		distance.put(source, 0);
		que.add(source);

		while (!que.isEmpty()) {
			String u = que.poll();
			visited.put(u, true);
			for (String v : g.get(u)) {
				if (v.equals(distination))
					return distance.get(u) + 1;
				if (!visited.get(v)) {
					que.add(v);
					distance.put(v, distance.get(u) + 1);
				}
			}
		}
		return distance.get(distination);
	}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: