[SOLVED] CMPE250 Project4- Gridland

Description

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.

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 <= 10⁵, 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

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

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)