Shortest Path in a Grid

You are given a grid of size \(M \times N\) consisting of 0s and 1s. Cells with value 0 are passable, and cells with value 1 are impassable. The task is to find the shortest path from a given starting position to a target position using only up, down, left, and right moves.

The grid is represented in the following way:

• \(grid[i][j] = 0\) represents a passable cell.
• \(grid[i][j] = 1\) represents an obstacle.

You should compute the minimum number of steps required to go from the start cell to the target cell. If the start and target positions are the same, the answer is 0. If there is no valid path, print -1.

The distance (\(d\)) is defined as the number of moves: \[ d = \text{number of edges in the shortest path from start to target.} \]

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

1. The first line contains two integers \(M\) and \(N\), representing the number of rows and columns of the grid.
2. The next \(M\) lines each contain \(N\) integers (either 0 or 1) separated by spaces, representing the grid.
3. The following line contains two integers: the starting cell coordinates \(x_{start}\) and \(y_{start}\) (0-indexed).
4. The last line contains two integers: the target cell coordinates \(x_{target}\) and \(y_{target}\) (0-indexed).

outputFormat

Output a single integer to standard output (stdout): the length of the shortest path from the start cell to the target cell, or -1 if no path exists.

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

4