Shortest Path in a Grid

Given an \(N \times M\) grid, where each cell is either passable (0) or an obstacle (1), your task is to compute the length of the shortest path from the top-left corner (0,0) to the bottom-right corner (N-1, M-1). You may move in four directions: up, down, left, and right. If no valid path exists, output -1.

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space. Each of the next \(N\) lines contains \(M\) space-separated integers representing the grid. A cell with value 0 is passable while a cell with value 1 is an obstacle.

outputFormat

Output a single integer representing the length of the shortest path from the top-left corner to the bottom-right corner in the grid. If no such path exists, output -1.

3 3
0 0 0
1 1 0
0 0 0

4