Finding A Good Path
------- - ---- ----
Given a 2-dimensional array representing elevations of
a 2-dimensional map, determine the lowest and highest
points and whether there is a path between them that
does not go both up and down.
Input
-----
For each test case, first a line that gives the test
case name. Then a line of the form
M N
giving the number of rows (M) and columns (N) in the
array. Then M lines each containing one row of N num-
bers, which are the elevations at the corresponding map
point. The rows are numbered 1 through M from top to
bottom, and the columns are numbered 1 through N from
left to right.
5 <= M,N <= 100
0 <= array element <= 100
The test case name line is at most 80 characters. Input
ends with an end of file.
Output
------
For each test case, first an exact copy of the test case
name line. Then a single line of the form:
Lr Lc Hr Hc YESNO
where (Lr,Lc) is the (row,column) of the lowest point in
the array, (Hr,Hc) is the (row,column) of the highest
point in the array, and YESNO is the word:
yes If there is a path from the lowest point to
the highest point that never goes down.
no If there is no such path.
Specifically, the path starts at the lowest point and
can only go from a point to one of its 4-neighbors
(left, right, up, or down) that does NOT have a lower
elevation than the point.
Indices in the array begin with 1, so
1 <= Lr,Hr <= M
1 <= Lc,Hc <= N
Input will be such that there is a unique solution.
Sample Input
------ -----
-- SAMPLE 1 --
5 5
2 3 3 4 5
2 4 4 1 4
2 1 0 2 1
4 2 1 3 4
3 1 2 2 3
-- SAMPLE 2 --
5 5
2 3 3 4 5
3 4 4 1 4
2 1 0 2 1
4 2 1 3 4
3 1 2 2 3
Sample Output
------ ------
-- SAMPLE 1 --
3 3 1 5 yes
-- SAMPLE 2 --
3 3 1 5 no
File: goodpath.txt
Author: Shai Simonson
Editor: Bob Walton
Date: Sat Oct 6 02:48:31 EDT 2018
The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.