Neel Sinha is the fittest person in 2k10 Batch.He tries every adventure sports now and then.
This time Mountaineering caught his attention.He is trying it for a few days now and enjoys on getting to high altitudes to enjoy the spectacular views of the region.He is planning on a walk today that can get him as high an altitude as possible, but he is also afraid of the dark and want to get back back before it's dark.
You are given a map of the region which is a 2-D character array.The altitude of the landscape at position (i,j) is denoted by the
character present at (i,j).'A'-'Z' represents altitude values from 0-25 and 'a'-'z' represents values from 26-51. Neel starts off at the coordinates (0,0) and is planning to walk between points with integer coordinates. In each segment of his walk, he can walk to any of orthogonally adjacent point as long as the magnitude of difference in altitude is no greater than
threshold, otherwise the path is too steep.
He cannot walk on the path that is too steep regardless of whether he is going uphill or downhill.
If he walks from some point to another that is at equal or lower altitude then the time it takes to travel is 1.
If he walks to some point with a higher altitude then the amount of time it takes is equal to altitude difference squared.
For example if he moves from 5 to 9 and 4(9-5) <=
thresholdthen amount of time is 4^2 = 16 units of time.
If he were to walk the same above segment but in opposite direction, it would take 1 unit of time.
Your task is to find out altitude of the highest point Neel Sinha can reach given that total amount of time taken may not be greater than
First line contains
T (T<=111)denoting the number of test cases.
Each of the test cases starts with two integers
number of rows and columns in the landscape respectively.
Then follows R lines each containing C characters each denoting an Altitude as describes above.
It is then followed by 2 Integers denoting
have been described above.
A single Integer for each test case denoting the maximum altitude that can be reached.
Each character of input will be a lowercase or an uppercase alphabet.
Problem Setter: Arjun Singh Bhatia
Problem Tester: Shikhar Sharad
Note: Editorial can be found here