Shortest Path in a Grid

You are given a two-dimensional grid of size \(n \times m\) where each cell is either free or blocked. A free cell is represented by 0 and a blocked cell by 1. Your task is to compute the length of the shortest path from a given starting cell to an ending cell by moving up, down, left, or right. If there is no valid path, output \(-1\).

The grid is provided via standard input. The first line contains two integers \(n\) and \(m\) representing the number of rows and columns respectively. Then follow \(n\) lines each containing \(m\) space-separated integers (either 0 or 1), representing the grid. The next line contains two integers representing the starting coordinates (\(start_x\) and \(start_y\)). The final line contains two integers representing the ending coordinates (\(end_x\) and \(end_y\)).

The problem can be formally described as follows:

Given a grid \(G\) of size \(n \times m\), a starting point \(S = (start_x, start_y)\) and a destination \(T = (end_x, end_y)\), find the length of the shortest path from \(S\) to \(T\) such that each move is one of the four valid directions and it only passes through cells where \(G[i][j] = 0\). If no such path exists, return \(-1\).

Note: It is guaranteed that the input values are valid and the coordinates are zero-indexed.

inputFormat

The input is read from standard input and has the following format:

n m
row1
row2
... 
rown
start_x start_y
end_x end_y

Where:

• n and m are the number of rows and columns.
• Each of the next n lines contains m integers (0 or 1) separated by spaces, representing the grid.
• The next line contains two integers: the starting cell coordinates.
• The last line contains two integers: the target cell coordinates.

outputFormat

Output the length of the shortest path from the start cell to the end cell on a single line. If no valid path exists, output -1.

## sample

3 3
0 0 1
0 0 0
1 0 0
0 0
2 2

4