1034. Swim in Rising Water (Dijkstra / BS)

Given an n x n grid where grid[i][j] is the elevation of a cell, water rises so at time t you may stand on any cell with elevation <= t. Starting at (0,0), return the least time to reach (n-1,n-1), moving 4-directionally. This equals the minimum over paths of the maximum elevation on the path. The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the least time.

Examples

Input: {"grid":[[0,2],[1,3]]}
Output: 3
Explanation: Must cross elevation 3.

Input: {"grid":[[0]]}
Output: 0
Explanation: Start is the end.

Input: {"grid":[[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]}
Output: 16
Explanation: Optimal path peaks at 16.

Constraints

• 1<=n<=50
• distinct elevations 0..n*n-1

Asked by