Shortest Path in a Grid

Given a grid of size \( n \times m \) where each cell is either 0 (empty) or 1 (blocked), your task is to find the shortest path from the top-left corner to the bottom-right corner. Movement is restricted to the four cardinal directions: up, down, left, and right.

The path length is defined as the number of cells included in the path (including both the starting and the ending cells). If a valid path exists, output the length of the shortest path; otherwise, output \( -1 \).

inputFormat

The input begins with a line containing two integers n and m separated by a space.

This is followed by n lines, each containing m space-separated integers (0 or 1) representing the grid.

outputFormat

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

5 5
0 0 0 1 0
1 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0

9