Shortest Path in Binary Matrix

This problem requires you to determine the shortest path from the top-left corner to the bottom-right corner in a binary matrix. The matrix contains only 0s and 1s, and you are allowed to move only right or down, but only through cells that contain a 1. If there is no valid path, output -1.

The input starts with two integers representing the dimensions of the matrix followed by the matrix rows. Note that valid moves are only to the right or downward cells which have a value of 1. The answer should be printed to standard output.

inputFormat

The first line contains two integers (n) and (m) representing the number of rows and columns, respectively. Each of the following (n) lines contains a string of exactly (m) digits (either 0 or 1) representing a row of the binary matrix.

outputFormat

Output a single integer representing the length of the shortest valid path from the top-left to the bottom-right cell. If no such path exists, output (-1).## sample

3 3
110
010
011

5