Drone Navigation on a Grid

You are given a grid of dimensions \(N \times M\). Each cell in the grid is either 0 (representing a free space) or 1 (representing an obstacle). A drone is positioned at the top-left corner (cell \((0,0)\)) and needs to reach the bottom-right corner (cell \((N-1, M-1)\)).

The drone can move in four directions: up, down, left, and right. The task is to calculate the minimum number of moves required for the drone to reach its destination. Each move counts as a single step. If no valid path exists, output -1.

Formally, let \(\text{moves}\) denote the number of steps taken. Then, the answer is the smallest \(\text{moves}\) such that:

[ \begin{cases} (0,0) \rightarrow (N-1,M-1) \text{ is reachable with valid moves} \ \text{or} \ -1 \text{ if unreachable} \end{cases} ]

</p>

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers \(N\) and \(M\) separated by a space, representing the number of rows and columns in the grid.
• This is followed by \(N\) lines, each containing \(M\) integers (either 0 or 1) separated by spaces. Each integer represents a cell in the grid.

It is guaranteed that \(1 \leq N, M \leq 1000\).

outputFormat

Output a single integer to standard output (stdout):

• The minimum number of moves required for the drone to reach the bottom-right corner of the grid.
• If no such path exists, output -1.

## sample

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 1 0
0 1 1 1 0
0 0 0 0 0

8