Minimum Moves in Maze

You are given a maze represented by a 2D grid of size n × m. Each cell in the grid is either passable (denoted by 0) or blocked by an obstacle (denoted by 1). You start at the top-left corner (cell (0, 0)) and your goal is to reach the bottom-right corner (cell (n-1, m-1)). You may only move in the four cardinal directions: up, down, left, and right.

The task is to determine the minimum number of moves required to get from the starting cell to the destination. If it is impossible to reach the destination due to obstacles, output -1.

In an ideal obstacle-free maze, the number of moves would be given by the formula: $$moves = (n - 1) + (m - 1)$$. However, obstacles may force deviations from this optimal path.

inputFormat

The first line of input contains two integers n and m representing the number of rows and columns respectively. The following n lines each contain m space-separated integers (either 0 or 1) which represent the grid of the maze.

outputFormat

Output a single integer: the minimum number of moves required to reach the bottom-right corner of the maze. If the destination cannot be reached, output -1.

3 3
0 0 1
1 0 1
1 0 0

4