ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

University academic school olympiad in informatics 2019

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Survive the flood

Time limit: 2.0 second
Memory limit: 256 MB
Every rabbit knows what to do in case of a flood. All you need to do is to get to a point above the water level and wait for Mazai. But when the actual flood happens, rabbits start to panic. That’s why we ask for your help to create an optimal evacuation plan for rabbits.
Let’s describe the flood as a game between a rabbit and water. Game takes place in a rectangular grid with n rows and m columns. Let’s say that a point in a row i and a column j has coordinates (i, j). It is known, that for all 1 ≤ in, 1 ≤ jm a cell with coordinates (i, j) has height hij. The rabbit starts at a point with coordinates (r1, c1), water starts at point with coordinates (r2, c2). Moreover, the rabbit has a property named jump height.
The rabbit and water take turns, the rabbit makes the first move. After each move the rabbit either doesn’t move or jumps to any adjacent cell. Cells are adjacent, if they have a common side. In addition to this, the rabbit cannot move to a cell, which height exceeds the height of a current cell more than on jump height. Water just fills all the cells that have adjacent cell filled with water of greater or equal height. Both water and the rabbit should stay within the game grid.
Rabbit can only survive in the cells not filled with water. The game doesn’t ever stop. Your task is to find the minimum jump height the rabbit needs to have in order to survive for infinite time.


First line of input contains 2 integer numbers n and m separated with a space (1 ≤ n, m ≤ 100, n · m1 ) — size of the game grid.
The next n lines describe grid cells. Each of n strings contains m integer numbers, separated with a space hij (0 ≤ hij ≤ 105) — heights of cells.
The next line contains two integer numbers r1 and c1, separated with a space (1 ≤ r1n, 1 ≤ c1m) — initial location of the rabbit.
The last line contains two integers r2 and c2, separated with a space (1 ≤ r2n, 1 ≤ c2m) — initial location of water.
It is guaranteed, that the rabbit and water start in different cells. Columns are numerated from 1 to m from left to right. Rows are numerated from 1 to n from top to bottom.


If the rabbit cannot survive in any case, in a single line output -1.
Otherwise, in a single line output a single number  — the least jump height that rabbit should have in order to survive for infinite time.


2 3
6 5 4
1 2 3
2 1
1 3
1 3
0 0 0
1 1
1 3
Problem Author: Anton Lipin
Problem Source: University academic school olympiad in informatics 2019
To submit the solution for this problem go to the Problem set: 2113. Survive the flood