Shortest Path in a Grid

You are given a grid of size m × n where each cell is either empty (denoted by 0) or blocked (denoted by 1). Your task is to determine the shortest path from the top-left corner (cell (0, 0)) to the bottom-right corner (cell (m-1, n-1)). You may move in the four cardinal directions: up, down, left, and right.

If a path exists, output the length of the path (i.e. the number of cells visited along the route). Otherwise, output -1.

Mathematically, if we denote the distance from the start to the end by \(d\), then you are to compute the minimum \(d\) subject to the condition that every step moves to an adjacent cell in the grid that is not blocked.

inputFormat

The input is read from standard input. The first line contains two integers m and n (1 ≤ m, n ≤ 100), indicating the number of rows and columns, respectively. The following m lines each contain n space-separated integers (either 0 or 1), representing the grid configuration. A value of 0 indicates an empty cell, and 1 indicates a blocked cell.

outputFormat

Print a single integer to standard output: the length of the shortest path from the top-left corner to the bottom-right corner if such a path exists; otherwise, print -1.## sample

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

9