Shortest Path in a Grid

You are given an n x m grid where each cell contains either a 0 or 1. A 0 indicates a road (an accessible intersection), while a 1 indicates a block. Your task is to determine the number of intersections visited in the shortest path from the top-left cell (0, 0) to the bottom-right cell (n-1, m-1). The path can only traverse through cells containing 0.

If either the starting cell or the destination cell is blocked (i.e. equals 1), or if no path exists, output -1.

The moves are allowed in four cardinal directions: up, down, left, and right.

Note: The number of intersections is defined as the number of cells visited along the path including the start and the destination. In mathematical terms, if the path visits k cells, then k is the answer. For example, if k = 7, then the path goes through 7 intersections. The path length is thus represented as:

\( \text{Length} = k \)

inputFormat

The input is given via standard input (stdin) and has the following format:

<n> <m>
row1_element1 row1_element2 ... row1_element_m
row2_element1 row2_element2 ... row2_element_m
... 
rown_element1 rown_element2 ... rown_element_m

Where:

• n is the number of rows in the grid.
• m is the number of columns in the grid.
• Each of the following n lines contains m space-separated integers (either 0 or 1).

outputFormat

Output a single integer via standard output (stdout): the number of intersections in the shortest path from the top-left to the bottom-right cell. If no such path exists, output -1.

## sample

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

7