542. Swim in Rising Water

You are given an n x n grid where grid[i][j] is the elevation at that cell. At time t, the water level is t and you can swim between adjacent cells (up/down/left/right) only if both cells have elevation at most t. Starting at the top-left, return the least time t to reach the bottom-right. The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the minimum time to reach the bottom-right.

Examples

Input: {"grid":[[0,2],[1,3]]}
Output: 3
Explanation: Need water level 3 to reach the corner.

Input: {"grid":[[0]]}
Output: 0
Explanation: Already at the destination.

Constraints

• 1<=n<=50
• grid is a permutation of 0..n*n-1

Asked by