Woburn Challenge 2001
Problem 1: The Rock
Losing the office pools would be an intelligence failure that would certainly cost M her job as chief of MI6. Resorting to means employed during the cold war, she decides to take action on several fronts. She decides to foment a revolution on Survivor Island to kick out the current dominant player and install her choice (Amber) as the winner of Survivor. She quickly deploys John Patrick Mason (a crack commando of the Special Air Service, SAS), a veteran of inserting onto ex-prison islands (his last mission was on Alcatraz). His job would be to infiltrate Survivor Island (Australia) and take the necessary measures to ensure that the "right" contestant would win.
Mason paradrops onto the island at night at a designated coordinate and inexplicably blurts out to no one in particular, "Welcome to the Rock." He has been provided with a rather strange map to the main camp. At each coordinate on the map, a number is listed (1-9), that encodes the direction that he must next travel from that coordinate to reach the next coordinate. Note that the map was prepared by P, who isn't always sound of mind, and thus it might turn out that the directions given would lead him to fall of the island or go in circles (and since it is pitch-black he can't tell if he's about to fall off the island).
Consider the island to be an N by N grid with each coordinate labelled with an ASCII character. The map consists of an N by N grid with each coordinate labelled with a number from 1-9 (N=8, NE=9, E=6, SE=3, S=2, SW=1, W=4, NW=7), as shown below in Figure 1, indicating the direction to travel. Please note that 5 will never appear in the input, and does not correspond to any direction. Your job is to report the grid coordinates that John travels (i.e. a string of ASCII characters). If there is a circular path, report it. If he falls off the island, that is the end of the path.
The first line contains N, the size of the grid (1 ≤ N ≤ 100) and T, the number of test cases (starting positions). The next N lines show the labels of the island grid (each line contains N characters). The next N lines similarly show the directions on the grid that Mason should follow. The remaining T lines will each contain a test case in the form R C, (1 ≤ R,C ≤ N) the row and column that Mason is to start at (1 1 would be the northwest corner, N N would be the southeast).
For each starting position, describe the path that Mason follows by outputting the labels of the positions he walks along in the format shown below.
5 5 ABCDE GGHIJ LLMNO GQRST UVWXY 96666 32222 91222 89222 94444 1 1 1 2 2 5 3 3 2 1
A BCDE JOTYX then WVUQMR repeated MRWVUQ repeated G then LGLG repeated
Note: We are interested in knowing about how the path loops, not how the ASCII string loops: so for the fifth sample test case,
G then LG repeated
would all be wrong.
G then LGLGLGLG repeated
Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 23, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3