Project #4 Solution

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




 
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)


 
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)




 
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




 
Variable limits are as follows:




1 N; M 103 1 Q 105




1 height of a cell 109




 
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.





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




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







 
Warnings




 
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.









4