Minimum Steps in a Height-Constrained Grid

You are given a grid of size N × M where each cell contains an integer representing the height of the terrain. You need to determine the minimum number of steps required to move from the top-left cell at position (0, 0) to the bottom-right cell at position (N-1, M-1).

You can only move one cell at a time in the four cardinal directions: up, down, left, and right. However, a move from cell (i, j) to an adjacent cell (k, l) is allowed only if the absolute difference in their heights satisfies

If it is not possible to reach the bottom-right cell under these conditions, output -1.

Note: The starting cell (0, 0) is counted as the first cell in your path; hence, if the starting cell is the same as the ending cell, the number of steps is 0.

inputFormat

The input is given via stdin and has the following format:

• The first line contains two integers, N and M, separated by a space, which denote the number of rows and columns of the grid respectively.
• The next N lines each contain M space-separated integers representing the grid.

outputFormat

Print a single integer to stdout representing the minimum number of steps required to reach the bottom-right cell from the top-left cell. If there is no valid path, print -1.

3 3
1 2 3
2 3 4
3 4 5

4