Indian National Olympiad in Informatics

Related:

Online Programming Contest, 12-13 November 2005

IARCS home > OLYMPIAD

Basic Division

Problem 2: The Rolling Ball, (K Narayan Kumar, CMI)

Indraneel has installed a rather interesting piece of modern art at Siruseri. This sculpture consists of a set of concrete pillars of square crosssection of varying heights, placed next to each other.

The sculpture occupies a rectangular area M feet long and N feet wide. In this area, M × N pillars are placed, each of cross section 1 foot by 1 foot. These pillars are of varying heights and no two adjacent pillars have the same height. A description of such an artwork can be given as a M × N array of numbers. For example, here is a possible description of the pillars, where M=2 and N=3.

3  5  4
7  1  3

The top left position is numbered (1,1) and the bottom right position is numbered (M,N), which is (2,3) in this example. The number at position (i,j) in the table indicates the height of the pillar placed at position (i,j).

Much to Indraneel's distress, Lavanya has decided to use the sculpture as a toy. She places a tennis ball on top of one of the pillars and watches it roll down as much as it can. You may assume that the ball never stays on top of a pillar if any of its four neighbours are shorter. For each pillar she would like to know the longest sequence of steps that ball could take before it becomes stationary. A step consists of the ball falling from one pillar to one of its shorter neighbours.

For example, in the sculpture above, if the ball is placed on the pillar of height 5 it can roll down 3 steps by first going to the right to the pillar of height 4, then down to the pillar of height 3 and finally to the left to the pillar of height 1.

Given a description of the sculpture and the starting position of the ball, your task is to calculate the longest sequence of steps through which the ball can come down till it reaches a stationary position, namely a pillar that is shorter than all its four neighbours.

Input format

The first line of input contains two integers M and N indicating the number of rows and columns in the sculpture, respectively. This is followed by M lines of input, each containing N integers. The i^th integer on line j+1 gives the height of the i^th pillar in row j. Finally, line M+2 contains two integers indicating the row and column where the ball is initially located.

Output format

The output consists of a single line with a single integer indicating maximum number of steps that the ball may take before it comes to rest.

Test data

You may assume that M ≤ 60 and N ≤ 60 in 80% of the inputs. You may assume that M ≤ 1000 and N ≤ 1000 in all inputs.

Example

We now illustrate the input and output formats using the above example.

Sample input

Sample output