// Mon Oct 12 08:49:46 CDT 2015 // Solution to SCUSA Boggle // Greg Hamerly (hamerly@cs.baylor.edu) import java.util.*; public class boggle_hamerly { public static class Trie { public Trie child(char c) { int i = c - 'a'; return (0 <= i && i < children.length) ? children[i] : null; } // returns true if the called node can be culled, i.e. it has no // children public boolean remove(String s, int pos) { if (pos == s.length()) { isWord = false; } else { int i = s.charAt(pos) - 'a'; if (children[i].remove(s, pos + 1)) children[i] = null; } boolean parentHasChildren = isWord; for (int i = 0; (! parentHasChildren) && i < children.length; ++i) parentHasChildren |= (children[i] != null); return !parentHasChildren; } public void add(String s, int pos) { if (pos == s.length()) { isWord = true; return; } int i = s.charAt(pos) - 'a'; if (children[i] == null) children[i] = new Trie(); children[i].add(s, pos + 1); } /* public void print(StringBuilder b) { if (isWord) System.out.println(b); for (int i = 0; i < children.length; ++i) { if (children[i] != null) { b.append((char)('a' + i)); children[i].print(b); b.deleteCharAt(b.length() - 1); } } } */ public boolean isWord() { return isWord; } private Trie children[] = new Trie[26]; private boolean isWord = false; } public static void solve_recursive(char [][] board, int i, int j, Trie dict, Trie root, StringBuilder b, Set<String> found) { final char ALREADY_USED = '#'; if (i < 0 || j < 0 || i >= board.length || j >= board[i].length) { return; } if (dict.isWord()) { found.add(b.toString()); root.remove(b.toString(), 0); // so that we don't search for it again } char c = board[i][j]; Trie child = dict.child(c); if (child != null) { board[i][j] = ALREADY_USED; // so that we don't search the same board cell again b.append(c); for (int ii = -1; ii <= 1; ++ii) for (int jj = -1; jj <= 1; ++jj) if (ii != 0 || jj != 0) solve_recursive(board, i + ii, j + jj, child, root, b, found); b.deleteCharAt(b.length() - 1); board[i][j] = c; } } public static void solve(char [][] board, Trie dict) { TreeSet<String> found = new TreeSet<String>(); StringBuilder b = new StringBuilder(); for (int i = 0; i < board.length; ++i) for (int j = 0; j < board[i].length; ++j) solve_recursive(board, i, j, dict, dict, b, found); for (String s : found) { System.out.println(s.replaceAll("q", "qu")); dict.add(s, 0); // replace words that were removed during search } } public static void check(boolean condition) throws Exception { if (!condition) throw new Exception("Input validation failed"); } public static void main(String args[]) throws Exception { Scanner input = new Scanner(System.in); int w = Integer.parseInt(input.nextLine()); check(1 <= w && w <= 200); Trie dict = new Trie(); for (int i = 0; i < w; ++i) { String word = input.nextLine(); check(!word.matches(".*[^a-z].*")); if (!word.matches(".*(q[^u]|q$)")) { dict.add(word.replaceAll("qu", "q"), 0); } } for (int s = Integer.parseInt(input.nextLine()); s != 0; s = Integer.parseInt(input.nextLine())) { check(2 <= s && s <= 8); char board[][] = new char[s][]; for (int i = 0; i < s; ++i) { String line = input.nextLine(); check(line.matches("^[a-z]+$")); check(line.length() == s); board[i] = line.toCharArray(); } solve(board, dict); System.out.println("-"); } } }