/** * "Brute force" solution to "Puzzling" */ import java.util.*; /** * ordered pair of row, column number */ class Location { public int row, col; public Location(int r, int c) { row = r; col = c;} public String toString() { return "("+row+","+col+")"; } public boolean equals(Location l) { return (row == l.row && col == l.col); } } /** * Node class for graphs */ class Node { public String word; public ArrayList adj; public int index; public Node(int i,String w) { adj = new ArrayList(); word = w; index = i; } public boolean isadj(Node n) { boolean found = false; for (int i = 0; i < adj.size(); i++) { if (adj.get(i).equals(n)) { found = true; break; } } return found; } public void add(Node n) { if (!isadj(n)) { adj.add(n); if (!n.isadj(this)) n.add(this); } } } public class Puzzling { public static Scanner in = new Scanner(System.in); public static int n, m, l; //rows, cols, words public static char[][] board; // the input letters public static String word[]; // the words to be searched for public static boolean found[]; // found[i] is true once word[i] is found public static Location position[][]; // for each word, its locations public static Node[] graph; public static int covered; // num nodes covered by DFS public static boolean[] visited; // used by DFS public static int caseNum; public static void main(String[] args) { n = in.nextInt(); m = in.nextInt(); l = in.nextInt(); caseNum = 0; while (n > 0 || m > 0 || l > 0) { caseNum++; board = new char[n][m]; word = new String[l]; found = new boolean[l]; for (int i = 0; i < n; i++) { String line = in.next().toUpperCase(); for (int j = 0; j < m; j++) board[i][j] = line.charAt(j); } position = new Location[l][]; for (int i = 0; i < l; i++) { word[i] = in.next().toUpperCase(); position[i] = new Location[word[i].length()]; found[i] = false; //System.out.println("Reserving " + position[i].length + " positions for " + word[i]); } search(); // find the words buildgraph(); // construct the graph of the words //display(); // debug -- display info // showgraph(); // debug -- show graph // Solve the problem by brute force -- rather than checking // for biconnectivity (which is the elegant way), try removing // every vertex and check resulting graph for connectivity boolean solution = true; for (int i = 0; i < l; i++) { // remove i-th word and all edges from it. Essentially // this makes the graph a digraph and the i-th word a sink ArrayList tempadj = graph[i].adj; graph[i].adj = new ArrayList(); //System.out.println("Removing " + graph[i].word); //showgraph(); if (connected(i)) { // System.out.println("Connected"); } else { // System.out.println("Word " + word[i] + " can't be removed"); solution = false; break; } graph[i].adj = tempadj; } // System.out.println("Case " + caseNum + ": " + (solution?"Yes":"No")); System.out.println((solution?"Yes":"No")); n = in.nextInt(); m = in.nextInt(); l = in.nextInt(); } } /** * Search the puzzle for each word. Even though we are guaranteed * that each word appears exactly once, we have to watch out for * palindromes, which might seem to appear twice, once forward and * once backward. */ public static void search() { for (int i = 0; i < l; i++) { String w = word[i]; // first, look in rows: // forward: for (int j = 0; j < n; j++) { // j = row for (int k = 0; k <= m-w.length(); k++) { // k = starting col int p = 0; while (p < w.length() && board[j][k+p] == w.charAt(p)) { //System.out.println("Found " + w.charAt(p) + " at " + j + " " + (k+p)); p++; } if (p == w.length()) { found[i] = true; for (int q = 0; q < w.length(); q++) position[i][q] = new Location(j,k+q); } } } // backward: if (!found[i]) { for (int j = 0; j < n; j++) { // j = row for (int k = m-1; k >= w.length()-1; k--) { //k = starting col int p = 0; while (p < w.length() && board[j][k-p] == w.charAt(p)) { //System.out.println("Found " + w.charAt(p) + " at " + j + " " + (k-p)); p++; } if (p == w.length()) { found[i] = true; for (int q = 0; q < w.length(); q++) position[i][q] = new Location(j,k-q); } } } } // Now look in columns: // Down: if (!found[i]) { for (int k = 0; k < m; k++) { // k = column for (int j = 0; j <= n-w.length(); j++) { // j = starting row int p = 0; while (p < w.length() && board[j+p][k] == w.charAt(p)) { //System.out.println("Found " + w.charAt(p) + " at " + (j+p) + " " + k); p++; } if (p == w.length()) { found[i] = true; for (int q = 0; q < w.length(); q++) position[i][q] = new Location(j+q,k); } } } } // Up: if (!found[i]) { for (int k = 0; k < m; k++) { //k = col for (int j = n-1; j >= w.length()-1; j--) { // j = starting row int p = 0; while (p < w.length() && board[j-p][k] == w.charAt(p)) { //System.out.println("Found " + w.charAt(p) + " at " + (j-p) + " " + k); p++; } if (p == w.length()) { found[i] = true; for (int q = 0; q < w.length(); q++) position[i][q] = new Location(j-q,k); } } } } // Diagonals: // NW to SE: if (!found[i]) { for (int k = 0; k <= m-w.length(); k++) { // k = column for (int j = 0; j <= n-w.length(); j++) { // j = starting row int p = 0; while (p < w.length() && board[j+p][k+p] == w.charAt(p)) { //System.out.println("Found " + w.charAt(p) + " at " + (j+p) + " " + (k+p)); p++; } if (p == w.length()) { found[i] = true; for (int q = 0; q < w.length(); q++) position[i][q] = new Location(j+q,k+q); } } } } // NE to SW: if (!found[i]) { for (int k = w.length()-1; k < m; k++) { // k = column for (int j = 0; j <= n-w.length(); j++) { // j = starting row int p = 0; while (p < w.length() && board[j+p][k-p] == w.charAt(p)) { //System.out.println("Found " + w.charAt(p) + " at " + (j+p) + " " + (k-p)); p++; } if (p == w.length()) { found[i] = true; for (int q = 0; q < w.length(); q++) position[i][q] = new Location(j+q,k-q); } } } } // SW to NE: if (!found[i]) { for (int k = 0; k <= m-w.length(); k++) { // k = column for (int j = n-1; j >= w.length()-1; j--) { // j = starting row int p = 0; while (p < w.length() && board[j-p][k+p] == w.charAt(p)) { //System.out.println("Found " + w.charAt(p) + " at " + (j-p) + " " + (k+p)); p++; } if (p == w.length()) { found[i] = true; for (int q = 0; q < w.length(); q++) position[i][q] = new Location(j-q,k+q); } } } } // SE to NW: if (!found[i]) { for (int k = w.length()-1; k < m; k++) { // k = column for (int j = n-1; j >= w.length()-1; j--) { // j = starting row int p = 0; while (p < w.length() && board[j-p][k-p] == w.charAt(p)) { //System.out.println("Found " + w.charAt(p) + " at " + (j-p) + " " + (k-p)); p++; } if (p == w.length()) { found[i] = true; for (int q = 0; q < w.length(); q++) position[i][q] = new Location(j-q,k-q); } } } } } } /** * Debugging */ public static void display() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) System.out.print(board[i][j]); System.out.println(); } for (int i = 0; i < l; i++) { System.out.println(word[i]); for (int j = 0; j < word[i].length(); j++) { System.out.print(position[i][j] + " "); } System.out.println(); } } /** * Builds a graph of connections between words */ public static void buildgraph() { // create an array of empty adjacency lists graph = new Node[l]; for (int w = 0; w < l; w++) graph[w] = new Node(w,word[w]); // two words are adjacent if they share a position in the grid for (int w1 = 0; w1 < l; w1++) { // first word index for (int w2 = w1+1; w2 < l; w2++) { // second word index //System.out.println("Comparing " + word[w1] + " to " + word[w2]); for (int i1 = 0; i1 < position[w1].length; i1++) { for (int i2 = 0; i2 < position[w2].length; i2++) { //System.out.println(" " + position[w1][i1] + "," + position[w2][i2]); if (position[w1][i1].equals(position[w2][i2])) { graph[w1].add(graph[w2]); break; } } } } } } /** * debugging -- prints in "dot" format */ public static void showgraph() { System.out.println("graph {"); System.out.println("overlap=false; splines=true;"); for (int w = 0; w < l; w++) { ArrayList a = graph[w].adj; for (int i = 0; i < a.size(); i++) { System.out.print(graph[w].word + " -- "); System.out.println(a.get(i).word + ";"); } } System.out.println("}"); } /** * test for connectedness via depth first search */ public static boolean connected(int omit) { // do a DFS from the first node, see if all nodes get covered: covered = 0; visited = new boolean[l]; for (int i = 0; i < l; i++) visited[i] = false; if (omit != 0) dfs(0); else if (omit == 0 && l > 1) dfs(1); else covered = 1; // Special case of only one word? I'd say it's okay return covered == l; } /** * recursive dfs */ public static void dfs(int v) { if (visited[v]) return; visited[v] = true; covered++; ArrayList adj = graph[v].adj; for (int i = 0; i < adj.size(); i++) { dfs(adj.get(i).index); } } }