Minimum Steps to Reach the End in a Grid

You are given a grid of size \(n \times m\) that represents a maze. Each cell in the grid is either empty (represented by 0) or an obstacle (represented by 1). Your task is to determine the minimum number of steps required to travel from the top-left corner (cell \((0,0)\)) to the bottom-right corner (cell \((n-1, m-1)\)). You may only move up, down, left, or right at each step and you cannot move diagonally. If either the start or the destination is blocked, or if there is no possible way to reach the destination, you should output -1.

The number of steps is defined as the number of moves you make. For example, in a 2x2 grid without obstacles, the minimum number of steps required is 2. Use a Breadth First Search (BFS) algorithm to compute the shortest path in the grid.

inputFormat

The first line of input contains two integers \(n\) and \(m\) which represent the number of rows and columns of the grid, respectively.

The following \(n\) lines each contain \(m\) integers, separated by spaces, representing the grid. Each integer is either 0 or 1, where 0 indicates an empty cell and 1 indicates an obstacle.

outputFormat

Output a single integer denoting 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.

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

6