Minimizing Maximum Elevation Difference

You are given an R x C grid of integer elevations. Your task is to find a path from the top-left cell (0,0) to the bottom-right cell (R-1,C-1) such that the maximum elevation difference between any two adjacent cells along the path is minimized.

You can move in the four cardinal directions: up, down, left, and right. The elevation difference between two cells having values \(a\) and \(b\) is defined as \(|a - b|\). Determine the smallest possible value for the maximum difference encountered along some valid path.

Note: Use the well-known Dijkstra's algorithm (or a variant) to solve this problem by considering the cost of a path as the maximum elevation difference observed so far.

inputFormat

The first line contains two integers, R and C, representing the number of rows and columns in the grid. The next R lines each contain C space-separated integers representing the elevations of the grid.

outputFormat

Output a single integer — the minimized maximum elevation difference along a valid path from the top-left to the bottom-right cell.## sample

3 3
1 3 2
4 6 5
7 8 9

3