favorite We need a little bit of your help to keep things running, click on this banner to learn more

Tourist Routes

Tourist Routes

Travel company decided to develop trails in the mountainous region. All the routes out of the collection point and end point of travel departure. Help develop as much as possible routes of minimal length. The length of the route - the number of cells, through which it passes.

Given a map of the area - an array of M×N, in every cell which recorded a positive integer - height of the terrain. Tourists will be able to move from one square to another through a common side, if the height difference does not exceed 1.


The first line contains 6 numbers M, N - size of the card, the coordinates of the point of collection A, B and the coordinates of left C, D (row number and column number). Further, written M rows by N of natural numbers - the altitude (the values do not exceed 100). M, N = 1..30.


In a single line display one number - the number of routes of minimal length, or -1 if it is impossible to lay such a route.

Time limit 1 second
Memory limit 64 MiB
Input example #1
4 5 1 1 2 5
1 2 3 4 6
2 2 2 2 2
3 2 1 2 4
5 2 2 3 1
Output example #1
Author Zhukovsky S.S.
Source Stage III All-Ukrainian School Olympiad 2010-2011, Round 1, Zhytomyr