Shortest Path in a Grid

You are given a grid-based game board represented as an m x n matrix. In this matrix, each cell contains either a 0 or a 1 where:

• 0 represents an empty cell, and
• 1 represents an obstacle.

Your task is to compute the length of the shortest path from the top-left corner (cell [0][0]) to the bottom-right corner (cell [m-1][n-1]). Moves are allowed only in four directions: up, down, left, and right. If no valid path exists, output -1.

The length of the path is defined as the number of moves taken. Formally, if a valid path exists, and its moves are represented by a sequence of adjacent steps, then the path length is given by the number of steps in that sequence.

Note: The problem can be formulated using the following BFS formulation: $$\text{distance}(x,y) = \min\{\text{distance}(prev) + 1\}\text{, for all valid moves}\$$

inputFormat

The first line of input contains two integers, m and n, representing the number of rows and columns in the grid. The following m lines each contain n integers (each either 0 or 1) separated by spaces, representing the grid.

outputFormat

Output a single integer: the minimum number of moves required to travel from the top-left corner to the bottom-right corner. If there is no valid path, output -1.## sample

3 3
0 0 1
0 1 0
0 0 0

4