Minimum Moves to Reach Destination

You are given a grid of size \(n \times m\). Each cell in the grid is either empty (represented by 0) or contains an obstacle (represented by -1). A robot starts at the top-left corner (cell (0,0)) and its goal is to reach the bottom-right corner (cell (n-1, m-1)) by moving only in the four cardinal directions (up, down, left, right). The robot cannot enter cells containing obstacles. Your task is to determine the minimum number of moves required for the robot to reach the destination. If it is impossible to reach the destination, output -1.

Input Constraints:

• \(1 \le n, m \le 10^3\) (for example purposes)
• Each cell value is either 0 or -1.

Note: A move is defined as moving one cell up, down, left, or right.

inputFormat

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

The following \(n\) lines each contain \(m\) space-separated integers (either 0 or -1) describing the grid.

outputFormat

Output a single integer: the minimum number of moves required to reach the destination, or -1 if it is impossible.

4 4
0 0 0 0
0 -1 0 0
0 -1 -1 0
0 0 0 0

6