Maximum Steps in Grid

You are given a two-dimensional grid of size \(m \times n\) where each cell contains either a 0 or a 1. A cell with a value of 1 is passable, while 0 indicates an obstacle. Your task is to determine the maximum number of steps in a simple path from the top-left corner (cell \((0,0)\)) to the bottom-right corner (cell \((m-1,n-1)\)). From any cell, you can move in one of four directions: up, down, left, or right. You cannot visit any cell more than once.

If there exists a valid path, output the number of steps taken on that path; otherwise, output \(-1\). Note: Although the description uses the term "maximum steps", based on the provided examples the intended solution finds the path that reaches the destination (which, for the given test cases, corresponds to the shortest valid path). For instance, in a full grid of 1's of size 100 \(\times\) 100, the expected output is 199 (i.e. \(100+100-1\)).

inputFormat

The first line contains two integers \(m\) and \(n\), representing the number of rows and columns in the grid respectively. This is followed by \(m\) lines, each containing \(n\) integers (either 0 or 1) separated by spaces, which represent the grid.

outputFormat

Output a single integer representing the number of steps in the path from the top-left corner to the bottom-right corner. If no such path exists, output \(-1\).

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

7