Shortest Path in a Grid

You are given a grid of size (n \times m) where each cell contains either a 1 (representing a street) or a 0 (representing a blockage). Your task is to determine the shortest path from the top-left corner (cell ((0,0))) to the bottom-right corner (cell ((n-1, m-1))) using only moves in the four cardinal directions: up, down, left, and right. If a valid path does not exist, output (-1).

inputFormat

The input is read from standard input (stdin). The first line contains two integers (n) and (m) separated by a space, representing the number of rows and columns. Each of the following (n) lines contains (m) integers (either 0 or 1) separated by spaces, depicting the grid.

outputFormat

Output a single integer on standard output (stdout): the length of the shortest path from the top-left corner to the bottom-right corner. If no such path exists, output (-1).## sample

3 3
1 1 0
0 1 1
1 1 1

5