Minimum Distance in a Matrix

Given a matrix \(G\) of size \(m \times n\), where each cell is either passable (denoted by 0) or blocked by an obstacle (denoted by -1), determine the minimum number of steps required to travel from the top-left corner (cell \((0,0)\)) to the bottom-right corner (cell \((m-1,n-1)\)). Movement is only allowed in the four cardinal directions: up, down, left, and right. If a valid path does not exist, or if the starting or ending cell is blocked, output -1.

Note: Each step moves from one cell to an adjacent cell. The distance is measured as the number of moves made.

inputFormat

The input is read from standard input (stdin). The first line contains two integers \(m\) and \(n\) — the number of rows and columns of the matrix, respectively. Each of the next \(m\) lines contains \(n\) space-separated integers representing the matrix cells; each cell is either 0 (passable) or -1 (obstacle).

outputFormat

Output a single integer to standard output (stdout): the minimum number of steps required to reach the bottom-right corner from the top-left corner. If there is no valid path, output -1.

3 3
0 0 0
0 -1 0
0 0 0

4