Class 09 - Graphs

Main00352TheSeasonalWar.java

package class09;
import java.io.BufferedReader;
import java.io.InputStreamReader;

// UVa 352 - The Seasonal War

public class Main00352TheSeasonalWar {

	public static void main(String[] args) throws Exception {
		new Main00352TheSeasonalWar().execute();
	}
	
	boolean v[][];
	boolean map[][];
	
	int dr[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
	int dc[] = { 1, 1, 0, -1, -1, -1, 0, 1 };
	
	public void dfs(int r, int c) {
		v[r][c] = true;
		
		// Visit all 8 nodes around this node
		// The dr and dc arrays take care of this by trying all directions
		
		for (int i = 0; i < 8; i++) {
			int rr = r + dr[i];
			int cc = c + dc[i];
			
			if (map[rr][cc] && !v[rr][cc]) {
				dfs(rr, cc);
			}
		}
	}
	
	public void execute() throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		String line = null;
		
		int tc = 1;
		
		while ((line = in.readLine()) != null) {
			int N = Integer.parseInt(line);
			
			map = new boolean[N+2][N+2];
			v = new boolean[N+2][N+2];
			
			// build the 2D grid map
			
			for (int r = 0; r < N; r++) {
				line = in.readLine();
				for (int c = 0; c < N; c++) {
					map[r+1][c+1] = line.charAt(c) == '1';
				}
			}
			
			// Every time that a 1 is encountered that hasn't been seen before, increase the eagle count and mark all
			// connected components so they are not double counted
			
			int count = 0;
			
			for (int r = 1; r <= N; r++) {
				for (int c = 1; c <= N; c++) {
					if (map[r][c] && !v[r][c]) {
						dfs(r, c);
						count++;
					}
				}
			}
			
			System.out.printf("Image number %d contains %d war eagles.\n", tc++, count);
		}
	}

}

Main10150Doublets.java

package class09;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

// 10150 - Doublets
// TLE on UVa

public class Main10150Doublets {

	public static void main(String[] args) throws Exception {
		new Main10150Doublets().execute();
	}
	
	public boolean areDoublets(String A, String B) {
		if (A.length() != B.length()) {
			return false;
		} else {
			int differences = 0;
			
			for (int i = 0; i < A.length(); i++) {
				int chA = A.charAt(i);
				int chB = B.charAt(i);
				
				if (chA != chB) {
					differences++;
				}
			}
			
			return differences == 1;
		}
	}
	
	public void execute() throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String line;

		// Read all the possible words in
		
		ArrayList<String> words = new ArrayList<String>();
		
		while ((line = in.readLine()) != null) {
			if (line.length() == 0) {
				break;
			}
			
			words.add(line);
		}
		
		// Initialize map
		
		HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
		
		for (String s : words) {
			map.put(s, new ArrayList<String>());
		}
		
		// Build map
		
		for (int i = 0; i < words.size(); i++) {
			String A = words.get(i);
			
			for (int j = i+1; j < words.size(); j++) {
				String B = words.get(j);
				
				if (areDoublets(A, B)) {
					map.get(A).add(B);
					map.get(B).add(A);
				}
			}
		}
		
		boolean first = true;
		
		while ((line = in.readLine()) != null) {
			String split[] = line.split(" ");
			
			if (split.length < 2) {
				break;
			}
			
			String A = split[0];
			String B = split[1];
			
			Queue<String> q = new LinkedList<String>();
			HashMap<String, String> prev = new HashMap<String, String>();
			
			q.add(A);
			prev.put(A, "");
			boolean found = false;
			
			while (!q.isEmpty()) {
				String s = q.poll();
				
				if (s.equals(B)) {
					found = true;
					break;
				} else {
					for (String ss : map.get(s)) {
						if (!prev.containsKey(ss)) {
							q.add(ss);
							prev.put(ss, s);
						}
					}
				}
			}
			
			if (first) {
				first = false;
			} else {
				System.out.println();
			}
			
			if (found) {
				Stack<String> stack = new Stack<String>();
				
				String s = B;
				
				while (s.length() > 0) {
					stack.add(s);
					s = prev.get(s);
				}
				
				while (!stack.isEmpty()) {
					System.out.println(stack.pop());
				}
			} else {
				System.out.println("No solution.");
			}
		}

	}

}