Apple trees in a garden form a rectangular grid. A group of monkeys lives on these
trees. Not more than one monkey lives in each tree. A monkey feels happy to believe that it is
the lord of all apple trees it views from the top of the tree it lives in. However, as the trees are
of different heights a monkey can view trees that are not obstructed from its view by other
trees. A monkey that views the maximum number T of trees is a lord of lords. The undisputed
monarch is the lord of lords that lives in the highest tree. In case two or more lord of lords
have the claim to be the monarch then monarchy is disputed.
Assume that the ground of the garden is plane; vertical straight lines represent trees;
trees are at a distance of unity row-wise or column-wise; and the height of each tree is an
integer in the unit of the distance. A tree of height zero in a position indicates absence of a
tree on that position. Visibility of a tree R from the top of a tree P depends on heights and
locations of P, R and other trees. A tree R is invisible from the top of a tree P if and only if
there exists a visible tree Q that lies on the vertical plane containing P and R and is located
between P and R so that the top of R is either on or below, the line joining tops of P and Q.
Write a program to locate the undisputed monarch, given heights of all trees.
The input may contain multiple test cases.
For each test case, the first line gives two integers m and n representing respectively
the total number of rows and columns of trees in the garden. Each of the next m lines
contains n integers representing heights of trees in a row. The jth integer in the ith row represents the height of the tree in ith row and jth column of the garden. Assume that the
garden contains no more than 200 trees.
The input terminates with an input 0 as the first input for a test case.
For each test case output three integers r, c and T in one line. Integers r and c
represent the location of the undisputed monarch, where r is the row number and c is the
column number of the tree on which the monarch lives. In case monarchy is disputed, both r
and c are zero. The integer T represents the total number of trees visible to a lord of lords.
3 3 1 2 3 4 5 6 7 0 9 3 4 4 4 4 4 4 4 4 4 4 4 4 4 1 10 5 3 2 1 6 4 2 8 7 1 0
2 2 7 0 0 10 1 5 6
Migrated from old NTUJ.
ICPC Kanpur, 2008
| No. | Testdata Range | Score |
|---|