Problem C
Hunting Pirates
The Atlantic Ocean has become extremely unsafe because of a recent increase in pirate activity (the Jolly Roger kind, not the free-digital-content kind). As a result, the Atlantic Counter-Piracy Collective (ACPC) is offering a substantial bounty for information about the travel route of any pirate ship. For too long these vessels have been elusive, and there have been few clues that could be used to capture them — until now. The ACPC has recently discovered several encoded maps among some flotsam, and each of these maps appears to show where one of the pirate ships travels.
The maps make use of an ancient encoding technique to hide the ships’ routes from the casual observer (or even from a determined observer who lacks the help of smart computer science students). A map consists of a grid of letters, with each grid position representing a square region of a much larger grid superimposed on the ocean’s surface. Along with these maps, the ACPC has come across a set of words in an old ship’s log. After much study, it has been determined that each word is associated with a certain map, and that finding that word in the map will directly reveal the travel route of the corresponding pirate ship.
Looking to collect multiple bounties, you have set yourself the task of finding the word hidden in each map. Finding a word in a map means finding a path of grid squares containing the letters of the word in order. This path can start at any grid square (as long as it contains the first letter of the word, of course), and at each step can proceed vertically, horizontally, or diagonally to a neighbouring square. Note that a path may contain repeated grid squares (since elusive pirates will use any trick at their disposal to confuse pursuers and evade capture).
The ACPC has adopted the convention that grid rows are numbered $1, 2, \dots $ from top to bottom, and grid columns are numbered $1, 2, \ldots $ from left to right. So, for example, suppose you are searching for the word “ARGHH”. If you start in position $(\textrm{row}, \textrm{column}) = (5,8)$ (because there’s an ‘A’ there), then you can look for the ‘R’ in any of the following $8~ \textrm{positions:}$
\[ (4,8) \ \ \ (6,8) \ \ \ (5,7) \ \ \ (5,9) \ \ \ (4,7) \ \ \ (6,7) \ \ \ (4,9) \ \ \ (6,9) \]The ACPC’s research is not perfect, though, so it is possible that a word thought to be hidden in a map cannot actually be found. In addition, a map may be fake (pirates also like to engage in disinformation), in which case there will be two or more paths in the map containing the word.
Input
The first line of input contains two space-separate integers, $R$ and $C,$ the number of rows and the number of columns in a map, respectively $(1 \leq R, C \leq 100).$ This is followed by the map in the form of $R$ lines containing $C$ characters each, where a character is an uppercase letter (A–Z). The map is followed by a line containing a word, which is a non-empty string of uppercase letters with length at $\textrm{most}~ 100.$
Output
If there is exactly one path in the map containing the word, print the positions of the grid squares in this path in order, one per line, using the same format as in the first sample output. If the map does not contain the word, print “Not found”. If the map contains the word more than once, print “Fake map!”.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 7 VAJLBVZ XRNOSNR GTFAOPK AWWIRCR KAAPHSX XWCVYCK SHIP |
(5,6) (5,5) (4,4) (5,4) |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 5 ABCDE ABCDE ABCDE ABCDE ABCDY BCDY |
Fake map! |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 3 CAT DOG CART |
Not found |
