Minimum Maximum Difference Path

You are given a grid of size \(n \times m\) where each cell contains an integer representing its altitude. Your task is to find a path from the top-left cell (\(0,0\)) to the bottom-right cell (\(n-1, m-1\)) such that the maximum absolute difference in altitude between any two adjacent cells along the path is minimized.

If there is no valid path that connects the top-left and bottom-right cells under the given conditions, output \(-1\). Otherwise, output the minimized maximum difference.

Note: The adjacent moves are allowed in the four cardinal directions: up, down, left, and right.

This problem can be solved using a binary search to determine the minimum acceptable difference, combined with a breadth-first search (BFS) to verify whether a valid path exists for a given maximum difference.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of rows and columns, respectively.

Each of the following \(n\) lines contains \(m\) integers representing the altitude values of the grid cells.

Input is read from stdin.

outputFormat

Output a single integer which is the minimized maximum difference along the path from the top-left to the bottom-right corner. If no such path exists, print \(-1\).

Output is written to stdout.

## sample

3 3
1 2 2
3 8 2
5 3 5

2