Shortest Path in Grid

You are given a grid of size \(N \times M\), where each cell contains either a 0 or a 1. A cell with a value of 0 is passable, and a cell with a value of 1 is blocked. Your task is to find the shortest path from a given start cell to an end cell by moving up, down, left, or right, without passing through blocked cells. If no such path exists, output -1.

The grid dimensions satisfy \(N\) rows and \(M\) columns. The start and end positions are provided as coordinates \((x_s, y_s)\) and \((x_e, y_e)\) respectively.

Note: The movement is allowed only in four directions. The length of the path is the number of moves made.

inputFormat

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

N M
row1
row2
... (N rows total)
start_x start_y
end_x end_y

\(N\) and \(M\) are integers representing the number of rows and columns respectively. Each row consists of \(M\) integers (0 or 1) separated by spaces. The start and end positions are represented by two integers each.

outputFormat

Output a single integer to stdout representing the length of the shortest path from the start position to the end position. If no such path exists, output -1.

4 4
0 0 1 0
1 0 1 0
0 0 0 0
0 1 1 0
0 0
3 3

6