Changyoung and the Commute Home

Interview

Time limit2sMemory limit512 MB

Summary

Given an N by N grid of elevations, find the smallest possible value of the maximum absolute elevation difference along a path from the top-left cell to the bottom-right cell, moving up, down, left, or right.

Level: Medium6 of 10
Topics: Binary search, BFS, Graph, Array
Solved: No attempts yet

Problem

Changyoung's commute home is a little different from his commute to work. For his health, he has gotten into the habit of renting a Ttareungyi bike and riding it home.

Changyoung's route home is represented as an N×N grid. Changyoung plans to travel from A1,1 to AN,N. He can move one cell at a time to a cell adjacent up, down, left, or right. Each cell Ar,c contains a positive integer, which is the elevation of that area. The absolute value of the elevation difference between adjacent cells is called the slope, and a larger slope means a steeper slope.

Ttareungyi bikes differ in performance according to price. An expensive bike can be ridden up a steep slope without dismounting, but a cheap bike is hard and dangerous on a steep slope, so the rider must dismount and walk.

Changyoung wants to rent a bike for the minimum cost and reach home without ever dismounting from it. To do so, he must know the minimum possible value of the maximum slope along the route he takes. Help Changyoung out.

Input

The first line gives the size of the grid, N.

From the second line, N lines give the elevation information of each cell. The first value given is A1,1, and the last value given is AN,N.

Output

Print the minimum value of the maximum slope along a route from A1,1 to AN,N.

Constraints

1 ≤ N ≤ 1,000
1 ≤ Ar,c ≤ 1,000,000,000

Examples2

Example 1
Input
```
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
```
Expected output
```
0
```
Example 2
Input
```
3
3 4 3
2 5 2
5 2 2
```
Expected output
```
1
```