Word Search

This problem involves those classic word search puzzles that you did when you were a kid (or maybe still do). The input will consist of several word search puzzles, each one consisting of a square grid of letters and a list of words to find. In this particular problem, your program should search for words up, down, left, and right. If a word is not found, a message should reflect this. You may assume that no word will be found more than once.

Input Specification

The input data will contain an arbitrary number of test cases, followed by a line containing a single 0. Each test case will have the following format:

The first line consists of a decimal integer N, between 5 and 10 inclusive, representing the dimensions of the grid. Following this are N rows of N capital letters. There are no spaces in the row, and each row is terminated by a newline character.

The next line consists of a decimal integer M, between 1 and 15 inclusive, representing the number of words to search for. Following this are M words, each word containing between 3 and 8 capital letters inclusive. There are no spaces within the words, and each word is terminated by a newline character.

There may or may not be one or more additional newline characters separating the test cases, or between the final test case and the terminating 0, but no superfluous newline characters will appear within a test case.

Output Specification

The test cases should appear in the output in the order in which they appear in the input. The output for each test case will consist of M lines (M defined above). Each line should begin with the word being searched for (and these words should appear in the output in the order in which they appear in the input). If the word is present in the grid, the word should be followed by the column number and the row number of the first letter in the word (the upper left corner is row 1, column 1) and the direction (U, D, L, R) in which the word is spelled out. There should be exactly one space between word and column, column and row, and row and direction. If the word is not present in the grid, the word should be followed by “WAS NOT FOUND”. Note that there is exactly one space between all words in this line. There should be one empty line following each test case in the output.

Sample Input

1. 5
2. ABCDE
3. HORSE
4. XYZAB
5. WOCQU
6. FOXES
7. 4
8. HORSE
9. COW
10. DOGS
11. BEE
13. 5
14. ELLPA
15. APLLA
16. ALLPE
17. PALEA
18. ELPPA
19. 3
20. APE
21. PEEL
22. APPLE
24. 0

download as text file

Output for Sample Input

1. HORSE 1 2 R
2. COW 3 4 L
3. DOGS WAS NOT FOUND
4. BEE 5 3 U
6. APE 1 3 D
7. PEEL WAS NOT FOUND
8. APPLE 5 5 L

download as text file

Original Problem

NMU Invitational Programming Contest, 2000