Minimum Moves to Reach Destination

Alice is navigating a grid represented as an n x m matrix. Each cell of the grid is either free (denoted by 0) or blocked (denoted by 1). She starts at the top-left corner (0, 0) and wants to reach the bottom-right corner (n-1, m-1). At each step, Alice can move one cell up, down, left, or right.

The task is to determine the minimum number of moves required for her to reach the destination. If the starting cell or the destination cell is blocked, or if there is no valid path through free cells, output -1.

In an ideal scenario without obstacles, the minimum number of moves is given by:

$$ moves = (n-1) + (m-1) $$

Note: The grid indices are 0-indexed.

inputFormat

The input is given via standard input. The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 1000), representing the number of rows and columns in the grid. Each of the next n lines contains m space-separated integers (each either 0 or 1), where 0 indicates a free cell and 1 indicates a blocked cell.

outputFormat

Output a single integer to standard output—the minimum number of moves required for Alice to travel from cell (0, 0) to cell (n-1, m-1). If the destination is unreachable, output -1.

4 4
0 1 0 0
0 0 0 1
1 0 1 0
0 0 0 0

6