Minimum Effort Path on a Grid

You are given an n × n matrix grid where each cell represents the height of a terrain. Your task is to find the minimum effort required to travel from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1). You can move up, down, left, or right. The effort of a path is defined as the maximum absolute difference between the heights of two consecutive cells along the path. Formally, if the path passes through cells (x_0, y_0), (x_1, y_1), ..., (x_k, y_k), then the effort is given by

[ \max_{0 \le i < k} \left| grid[x_{i+1}][y_{i+1}] - grid[x_i][y_i] \right| ]

Find a path that minimizes this effort.

inputFormat

The input is read from standard input. The first line contains an integer n (the size of the grid). The following n lines each contain n space-separated integers representing the grid's rows.

outputFormat

Output a single integer: the minimum effort required to travel from the top-left to the bottom-right cell.

3
1 2 2
3 8 2
5 3 5

2