Shortest Path in a Grid

You are given a 2D grid where each cell can either be an open space (represented by 0) or an obstacle (represented by 1). You are also provided with two pairs of coordinates: a start position and a target position. Your task is to determine the length of the shortest path from the start to the target, moving only up, down, left, or right. If the target is unreachable, output -1. Note that if the start and target are the same cell, the shortest path length is 0.

The allowed moves can be summarized by the following directions in \( \LaTeX \):

[ \begin{aligned} &\text{Up}:\ (-1,0)\ &\text{Down}:\ (1,0)\ &\text{Left}:\ (0,-1)\ &\text{Right}:\ (0,1) \end{aligned} ]

This problem requires an efficient breadth-first search (BFS) to explore the grid and compute the shortest path.

inputFormat

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

• The first line contains two integers \( R \) and \( C \) representing the number of rows and columns in the grid.
• The next \( R \) lines each contain \( C \) integers (either 0 or 1) separated by spaces, representing the grid.
• The following line contains two integers representing the starting coordinates (row and column), 0-indexed.
• The final line contains two integers representing the target coordinates (row and column), 0-indexed.

outputFormat

Print a single integer to stdout which is the length of the shortest path from the start to the target. If the target is unreachable, print -1.

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

4