Word Search

Project Details

        A popular diversion in the United States, word find (or word search) puzzles ask the player to find each of a given set of words in a square table filled with single letters. A word can read horizontally (left or right), vertically (up or down), or along a 45 degree diagonal (in any of the four directions) formed by consecutively adjacent cells of the table; it may wrap around the tables boundaries, but it must read in the same direction with no zigzagging. The same cell of the table may be used in different words, but, in a given word, the same cell may be used no more than once. Write a computer program for solving this puzzle.

       To make the problem more precise we shall use a fixed input and output format. The input to the program consists of the puzzle grid followed by a list of words. For each word the program should print out the row and column in the puzzle grid of the first character of the word. If the word does not exist in the puzzle, it should print out NOT FOUND.

       More specifically, the first line of the input is an integer R indicating the number of rows of the puzzle. R shall always be larger than 0 and no more than 100. The second line of the input is an integer C indicating the number of columns of the puzzle. C shall always be larger than 0 and no more than 100. This input is then followed by R lines of input containing C characters representing the puzzle grid. After the R lines is another number N representing the number of words to find. This is then followed by N lines with each line containing a word to search. In all cases, you can assume that the characters are all upper case.

     The output consists of N lines with each line being either the string NOT FOUND or two numbers separated by a space R C representing the row and column where the first character of the respective word can be found. For simplicity, we shall refer to the first row and first column as 0. Remember that, in this puzzle description, words can wrap around to the other side.

Input

Input Reference

6
8
ABBEJCDD
ULSCALAR
FUGLVRUT
STOUASTO
STOALGOT
LALGOSLU
8
SCALA
JAVA
ALGOS
ALGORITHM
SLUG
SLUR
GOES
TURTLE

row
column
Word Search Line 1
Word Search Line 2
Word Search Line 3
Word Search Line 4
Word Search Line 5
Word Search Line 6
Number of Words to Find
First Word to Search For
Second Word to Search For
Third Word to Search For
Fourth Word to Search For
Fifth Word to Search For
Sixth Word to Search For
Seventh Word to Search For
Eighth Word to Search For

Output

Output Reference

1 2

0 4

5 1

NOT FOUND

5 5

1 2

4 5
​
NOT FOUND

SCALA: First Letter: Row 1, Column 2

JAVA: First Letter: Row 0, Column 4

ALGOS: First Letter: Row 5, Column 1

ALGORITHM: N/A

SLUG: First Letter: Row 5, Column 5

SLUR: First Letter: Row 1, Column 2

GOES: First Letter: Row 4, Column 5

TURTLE: N/A

Word Search Class

Solve Word Search Class (Main Class)