Jumping Maze ------- ---- You've been given yet another maze to traverse. This one's a bit different. Its a grid and you can enter from the outside at any boundary square. Once you are at a square in the grid, you will find there an instruction as to what to do next. The possible instructions are: r:c Go to the grid square in column c of row r. m Go to ANY grid square whose Manhattan distance from the current square is EXACTLY m. X DIE!!! You Lose! G goal! Success! You Win! Here r, c, and m denote integers, whereas X and G denote the letters `X' and `G'. The Manhattan distance between square r1:c1 and square r2:c2 is defined to be |r1-r2| + |c1-c2|. As we said above, you start by moving to any boundary square. You want to win, of course; i.e., you want to move to a point with a G. You are not allowed to move outside the grid. If you go to a square from which the goal is unreachable, you lose. Input ----- A sequence of test cases. Each test case begins with a line containing the test case name. The next line has the form M N where the maze has M rows each with N columns. The next M lines each contain N instructions chosen from the ones above. The c'th instruction in the r'th line is the instruction for the square r:c. 2 <= M, N <= 1,000 sum M*N over all test cases <= 1,000,000 1 <= r <= M 1 <= c <= N 1 <= m <= M + N In any test case there will be exactly one G, and it will be reachable from some boundary square. Input ends with an end of file. The test case name line is at most 80 characters. Output ------ For each test case, first an exact copy of the test case name line. Then just one line containing the coordi- nates of your path to the goal, in the form `r:c'. The first entry should designate the boundary square at which you enter the maze, and the last should designate the square containing G. Input will be such that there is always a solution. YOUR SOLUTION SHOULD BE THE SHORTEST. If there are several shortest solutions, any one will do. Display ------- The input and output can be displayed in X-Windows or printed by the commands display_maze sample.in [sample.test] print_maze sample.in [sample.test] where sample.test is the output file corresponding to sample.in, and these files can be replaced by any test case input file and its corresponding output. The output file can be omitted in which case only the input will be displayed. Sample Input ------ ----- -- SAMPLE 1 -- 5 5 1:1 1:1 1:1 1:1 1:1 1:1 3:3 1:1 1:1 1:1 4:2 1:1 G 2:2 1:1 1:1 3:4 1:1 1:1 1:1 1:1 1:1 1:1 1:1 1:1 -- SAMPLE 2 -- 9 9 3 4:8 5:5 4:5 6:6 3 X 2:9 5:2 X 6:5 2:2 9:8 2:3 1:1 X 4 3 3 X 8:1 4 2:6 7:6 1:2 9:7 5:9 9:2 9:1 X X 8:6 3:1 5:3 8:4 4 4 X 4 8:8 4:6 8:3 9:8 1:1 4:2 X 6:8 7:3 4 3 3 X 4:2 X 3:7 4 9:7 4 4:2 3:2 4:5 3 9:8 8:1 3 2:5 7:8 5:1 1:5 3:5 G 7:8 6:5 3:5 9:2 3 5:3 8:4 3 7:5 4 Sample Output ------ ------ -- SAMPLE 1 -- 3:1 4:2 3:4 2:2 3:3 -- SAMPLE 2 -- 1:5 6:6 5:4 8:8 File: jmaze.txt Author: Bob Walton Date: Mon Oct 14 01:00:37 EDT 2019 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file.