Update appNew update is available. Click here to update.

Path With Maximum And Minimum Value

Last Updated: 27 Mar, 2021
Difficulty: Easy


Try Problem

Given a matrix of integers ‘ARR’ with ‘R’ rows and ‘C’ columns, find the maximum score of a path starting at [0, 0] and ending at [R-1, C-1]. The score of a path is the minimum value in that path. For example, the value of the path 8 -> 4 -> 5 -> 9 is 4. A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).


Let’s say we have ARR = { {5 4 5} , {1 2 6} , {7 4 6}} so the path with 
maximum value will be 5 -> 4 -> 5 -> 6 -> 6 and we have to return 
the minimum value in this path as the answer i.e 4.
Input format:
The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains two integers ‘R’ and ‘C’ denoting the number of rows and columns respectively.

Then the remaining input is of R lines where each line contains C space-separated numbers denoting the elements of the RXC sized matrix ‘ARR’.
Output format:
For each test case, return the minimum value in the maximum path.

Output for each test case is printed on a separate line.
You do not need to print anything, it has already been taken care of. Just return the minimum value in the maximum path.
1 <= T <= 10
1 <= R , C <= 100
0 <= ARR[i][j] <= 10^9

Time Limit: 1 sec