All submissions for this problem are available.
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
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.
1 2 3
4 5 6
7 0 9
4 4 4 4
4 4 4 4
4 4 4 4
5 3 2 1 6 4 2 8 7 1
2 2 7
0 0 10
1 5 6
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, CS2, PAS fpc, PAS gpc, RUBY, PHP, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, SQL, TEXT|
Fetching successful submissions