Minimum Steps in a Maze

You are given a maze represented by a matrix of size \(n \times m\), where each cell contains either a 1 or a 0. A cell with a 1 denotes an open path, while a 0 indicates a blocked cell. Your task is to determine the minimum number of steps required to travel from the top-left corner of the matrix (cell \( (0,0) \)) to the bottom-right corner (cell \( (n-1, m-1) \)).

You can move one step at a time in any of the four directions: up, down, left, or right. Movement through cells containing 0 is not allowed. If there is no valid path from the start cell to the destination, output \(-1\). In the special case where the matrix consists of a single cell with a 1, no movement is required and the output is 0.

Note: The number of steps is defined as the number of moves from one cell to an adjacent cell along the shortest valid path.

inputFormat

The input is given via standard input (stdin) as follows:

1. The first line contains two integers \(n\) and \(m\), separated by a space, representing the number of rows and columns of the matrix respectively.
2. The following \(n\) lines each contain \(m\) integers (either 0 or 1) separated by spaces, representing the rows of the matrix.

outputFormat

Output a single integer to standard output (stdout) which is the minimum number of steps required to reach the bottom-right corner from the top-left corner. If no valid path exists, output \(-1\).

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

6