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.