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.

Figure 1

Input

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).

Output

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.

Sample Input

5 5
ABCDE
GGHIJ
LLMNO
GQRST
UVWXY
96666
32222
91222
89222
94444
1 1
1 2
2 5
3 3
2 1

Sample Output

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, GL repeated, G then LG repeated, GLGL repeated, and G then LGLGLGLG repeated would all be wrong.

All Submissions
Best Solutions

Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 23, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

A bound on T would be nice.

1 <= T <= 10

Shouldn't T in the sample be 3?  
Or are 2 starting points missing?

and the Note says that it should be G then LGLG repeated. 
why then, isn't the fourth testcase M then RWVUQM repeated?

Read the note more carefully, it explains the difference between "M then RWVUQM repeated" and "MRWVUQ repeated".

oooh i get it
I was looking at the wrong starting point for "G then LGLG repeated" (4,1 instead of 2,1). ok i get it :)