Minimum Cell Modifications to Ensure a Valid Path

You are given an m x n grid of integers. A cell with a value of -1 is considered blocked, while any other value is free. Starting from the top-left cell (0-indexed) and moving only down or right, determine whether there exists a path to the bottom-right cell.

You are allowed to modify at most one blocked cell (i.e. a cell with value -1) by changing it to any integer in the range \( [0, 1000] \). Your task is to output the minimum number of modifications (either 0 or 1) required to create a valid path. If even after one modification no valid path can be formed, output -1.

Note: A valid path must move only down or right at each step.

inputFormat

The first line contains two integers, \( m \) and \( n \), representing the number of rows and columns in the grid.

Each of the next \( m \) lines contains \( n \) space-separated integers, representing the grid.

Input Format:

m n
row1_element1 row1_element2 ... row1_element n
...
rowm_element1 rowm_element2 ... rowm_element n

outputFormat

Output a single integer representing the minimum number of cell modifications needed to create a valid path from the top-left to the bottom-right corner. Output 0 if a path already exists, 1 if one modification is sufficient, or -1 if a valid path cannot be formed even after one modification.

3 3
1 1 -1
-1 1 1
2 2 1

0