Input File: huntin.txt
Output File: huntout.txt
Time Limit: 0.333 second
A young friend has become quite interested in Hunt-a-Word puzzles, where one is given a rectangular block of letters, e.g.
XSMILEA FHKDLDB ISMIOQP XDMFLGE LSKLYEH
and asked to locate a word, such as
DOG. In this example,
DOG can be found beginning in row 2, column 4 and heading
south-east (down and right).
Your friend is continually asking you for help on these puzzles, and you decide it would be good to write a program to help them and so allow you to concentrate on your school work.
Your task is to write a program which finds each word from a given
list of words in a given block of letters. Note that words can
occur more than once, in which case your program may find either
occurrence. In the example above, the word
SMILE occurs twice - once at row 1, column 2 and heading east,
and once at row 5, column 2, and heading north-east.
Words may lie in any one of eight possible directions,
NW N NE \ | / \|/ W --+-- E /|\ / | \ SW S SE
but must run in a straight line. For example,
be found at row 3, column 2 in the example above - it does not run
straight in one of the eight possible directions.
The first line shall consist of a pair of positive integers h w, separated by a single space, where h is the height (number of rows) of the block, and w is the width (number of columns) of the block. Each of h and w shall be at most 100.
Following this is the block of letters. There shall be exactly h
lines, each consisting of exactly w characters and a single terminating
newline. Each character shall be an upper case letter,
Following this is a line with a single positive integer n, giving the number of words which need to be found in the grid. The integer n shall be at most 100.
Following this are n lines, each containing a word to be found
on a single line together with a terminating newline.
The word shall consist of at most
100 characters, each of which shall be an upper case letter,
Every supplied word shall occur at least once in the given block of letters.
Other than the space separating the integers h and w on the first line of input, there shall be no other space characters in the input file.
You program shall output a sequence of finds, one to a line, where each find gives a location of a supplied word in the given block of letters. The finds shall be in the same order as the supplied words. In the event a word occurs multiple times in the grid, you should output only one location at which it is found (it does not matter which one).
A find shall consist of a two positive integers r c
followed by a direction. The positive integers give the row (r) and
column (c) in which the word starts. Both rows and columns are numbered
so that the top left letter in the block is in row 1 and column 1. The
direction shall be one of
NW in accordance with the compass diagram shown above.
5 7 XSMILEA FHKDLDB ISMIOQP XDMFLGE LSKLYEH 1 DOG
2 4 SE
5 7 XSMILEA FHKDLDB ISMIOQP XDMFLGE LSKLYEH 3 SMILE DOG ADO
1 2 E 2 4 SE 1 7 SW
Your program will receive 100% for correctly locating one occurrence of each supplied word. Programs which do not correctly locate all supplied words shall receive proportionally less marks. For example, a program which correctly finds only 3 of 4 supplied words will receive 75%.
Note that the finds must be in the same order as the list of supplied words! If the finds are output in the incorrect order, they may not be legitimate finds of the corresponding word, and will not count as a correct find!