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.
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 |
