Problem 4: Lost in Space

Description

This program should search for strings in an N by N array of characters. In the context of this problem, a "character" is any printable ASCII character (ASCII values 32 thru 126, inclusive).

The input file SPACE.IN contains the following:

• line 1: the value of N (<= 50),
• lines 2 to N+1: N-character-long strings, possibly including blanks, (However please note that since some PC editors automatically truncate trailing blanks, none of the lines in the file SPACE.IN will contain trailing blanks. That is, every line will end with some non-blank character. Leading & imbedded blanks are permissible.)
• lines N+2 through end of file: strings 1 to N characters long, containing no blanks.

Lines 2 through N+1 of the file represent the contents of the N by N array, line 2 for row 1, line 3 for row 2, etc.

For Line N+2 and after, you are to determine each (and every) position at which the string appears in the array. "Appears" means that the first character of the string matches the character at the position, and that subsequent characters in the string match the characters in the array (skipping over any blanks in the array) going in any of the eight possible directions E (right), NE (diagonally up and right), N (up), NW (diagonally up and left), W (left), SW (diagonally down and left), S (down), and SE (diagonally down and right). The string you are looking for may not "wrap around" from one edge of the array to another.

The output for each string will be:

• a blank line
• the string itself
• Either the message "not found"
  OR
  A listing of every starting position and direction at which the string is found, using the format: (row,column) - dir [for example, (5,3) - NW]

If the string appears more than once, you must report each occurrence. The order in which you report multiple occurrences is not important.

Example input:

4
LOST
I  N
SP A
C  E
ANT
LOT
S
PT

Example output:

ANT
(3,4) - N

LOT
not found

S
(1,3) - N
(1,3) - NE
(1,3) - E
(1,3) - SE
(1,3) - S
(1,3) - SW
(1,3) - W
(1,3) - NW
(3,1) - N
(3,1) - NE
(3,1) - E
(3,1) - SE
(3,1) - S
(3,1) - SW
(3,1) - W
(3,1) - NW

PT
(3.2) - NE