Starting from:

$30

CMPE250-Assignment 4 Solved

Mahir lives in Gridland. Gridland consists of N rows and M columns where every point has a height. To go from one cell to it’s adjacent ones Mahir needs a ladder which is at least as long as the height difference. For example to go from a cell which has height X to a cell which has height Y Mahir needs a ladder at least |X-Y| units long. Mahir is curious, he wants to know the the shortest ladder which allows him to go from one given cell, X, to the other, Y.

3
2
4
5
From (1,2) to (2,2) via (1,1) and (2,1), 1 unit length of ladder is sufficient.

Important Notes:

•    Mahir can only travel from a cell to it’s adjacent ones in a single step.(i.e he can go 4 directions which are left,right,bottom and up.)

•    The upper leftmost cell is (1,1) and the bottom rightmost cell is (N,M).

BONUS: You will be given Q queries, asking the minimum length of the ladder that Mahir can travel from a given cell to the other one. Correctly answering the case when Q = 1 will give you the maximum point. If your code correctly works in the time limitation for the case when 1 < Q <= 105, your name will be added to the bonus list.

1           Input/Output Format
1.1         Input Format
The first line of the input file holds two integers, N and M, showing the number of rows and the number of columns respectively.

In the following N lines, heights of cells are given, M integers in every line.

In the following line, number of queries Q is given.

Then, the next Q lines will have 4 integers indicating two cells of a query.

1.2         Output Format
Print the answer for the each query, minimum length of the ladder that Mahir can travel from a cell to the other one, in a new line.

2           Examples
1.    Sample Input

5    5

1 2 3 4 5

100 100 23 100 100

100 100 43 100 100

100 100 63 100 100

100 100 83 100 100

1

1 1 5 3

Sample Output

20

Explanation

(1,1) → (1,2) → (1,3) → (2,3) → (3,3) → (4,3) → (5,3)

2.    Sample Input

5    5

1 2 3 4 5

100 100 23 100 100

100 100 43 100 100

100 100 63 100 100

100 100 83 100 100

2

4 2 4 4

1 1 1 5

Sample Output

17

1

Explanation

•    First query,(4,2) → (5,2) → (5,3) → (5,4) → (4,4)

•    Second query,(1,1) → (1,2) → (1,3) → (1,4) → (1,5)

More products