Description

Jenny Cub is a cute little bear who loves to eat honey. To figure out how much honey will be produced by her bee friends, she counts the number of flowers in Roseland Park; the size of the honey yield depends on the type of flower the bees use.

Since Jenny Cub is a young and forgetful bear, she has created maps of the locations of the honey plants by marking which areas contain which flowers. Unfortunately, her little sheep Baa-Baa has jumbled up her maps so she can no longer spot the flowers. She needs you to search through her series of maps to find the locations of her honey plants.

Input

The input begins with a positive integer indicating the number of maps followed by a blank line. Each map starts with two integers (r, c) representing the number of rows and columns in the grid. This is followed by the grid itself, which is composed of r rows of c characters. Next, another integer n indicates the number of flowers to find, followed by the names of the flowers. If there is another map in the series, then a blank line preceeds the next one. A sample input is as follows:

1

8 9
abcdefghi
fdaiSieSf
hlrthagup
dromuinNo
aTssClDOi
haeMyVIqr
OpsRdklpj
AgqIhmOpS
4
Daisies
Roses
Goldenrods
Tulips

Output

Your job is to help Jenny Cub locate the flowers in the word jumble. The flowers can be in any of the eight horizontal, vertical, and diagonal directions and case does not matter. Output the locations of the flower as in the following sample output:

Map 1
Daisies (2, 2) (2, 8)
Roses (3, 3) (7, 3)
Goldenrods Not Found
Tulips (3, 4) (8, 9)

Use a blank line to separate the outputs of different maps. If a flower is not found, report "<FlowerName> Not Found", otherwise report the name of the flower followed by the start and end location of the word in the grid.

Approach

After reading in the grid into a two-dimensional array, search for each word in the map. Do this by scanning each character until we match the first letter in the word. When this is found, search in all eight directions. The search mechanism is the same for all directions; only the rstep and cstep change for each direction. If the flower is found, then report the start and end coordinates. Otherwise continue to search the rest of the map. If the flower is not found, output Not Found.

Input/Output

• Final Input: problem002.input
• Final Output: problem002.output

Source Code

• Peter Bui's source code: pbui.c
• Stephen Lagree's source code: slagree.cpp