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). Input Input starts with an integer on a line by itself containing the number of datasets, followed by a blank line. Each dataset 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 input file will contain trailing blanks. That is, every line will end with some non-blank character. Leading and 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. Output The output for each string in each dataset 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 have to output multiple occurrences is: first by increasing row number, second by increasing column number when same row and finally (when both row and column are equal) by direction in clockwise order, beginning with the North. Print an extra blank line between datasets.
2/2 Sample Input 1 4 LOST IN SP A CE ANT LOT S PT Sample 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