Get a Free Quote

Solved-Assignment 4- Solution

$30.00 $19.00

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 di erence. For example to go from a cell which has height X to…

You’ll get a: . zip file solution

 

 
Categorys:
Tags:

Description

5/5 – (2 votes)

  • 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 di erence. For example to go from a cell which has height X to a cell which has height Y Mahir needs a ladder at least jX-Yj 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.

  • 2

  • 5

From (1; 2) to (2; 2) via (1; 1) and (2; 1), 1 unit length of ladder is su cient.

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.

  • Input/Output Format

2.1 Input Format

The rst line of the input le 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.

2.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.

  • Examples

    1. Sample Input

5 5

12345

100 100 23 100 100

100 100 43 100 100

100 100 63 100 100

100 100 83 100 100

1

1153

Sample Output 20

Explanation

(1; 1) ! (1; 2) ! (1; 3) ! (2; 3) ! (3; 3) ! (4; 3) ! (5; 3)

  1. Sample Input

5 5

12345

100 100 23 100 100

100 100 43 100 100

100 100 63 100 100

100 100 83 100 100

2

4244

1115

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)

  • Grading

Grading of this project is based on the success of your code in test cases. Your score will be the sum of collected points from each test case. Each test case will have equal weight. Maximum score is 100. If you successfully solve the bonus case, your name will be noted and this will be considered when giving the letter grades.

  • Implementation Details

    1. Variable limits are as follows:

1 N;M 103 1Q105

1 height of a cell 109

    1. Execution time limit is 2 seconds. If your code runs more than 2 seconds on a test case you will get 0 points from that test case.

  1. Your program will be compiled with cmake CMakeLists.txt && make command.

  1. I will execute your program with ./project4 inputFile outputFile command.

  • Warnings

    1. Make sure an executable is created after executing cmake CMake-Lists.txt && make commands. Otherwise, no executable will be created and your code will fail in grading.

  • Submission Details

You are supposed to use the Github Classroom system provided to you for all projects. No other type of submission will be accepted.