Shortest Path in a Grid

You are given a grid of integers with 0 representing an empty cell and 1 representing an obstacle. Your task is to find the length of the shortest path from a starting position to a target position. You may only move up, down, left, or right. If the target is unreachable, output -1.

The grid can be represented as a matrix, and the movement is restricted to the four cardinal directions. Formally, given a grid \(G\) of size \(R \times C\), a starting position \(S = (s_r, s_c)\) and a target position \(T = (t_r, t_c)\), you are to compute the minimum number of moves needed to reach \(T\) from \(S\). If no valid path exists, output \(-1\).

Input Format: The first line contains two integers \(R\) and \(C\) denoting the number of rows and columns. The next \(R\) lines each contain \(C\) integers (either 0 or 1) representing the grid. The following line has two integers representing the starting coordinates \(s_r\) and \(s_c\), and the next line contains two integers representing the target coordinates \(t_r\) and \(t_c\).

Output Format: Print a single integer that is the length of the shortest path from the start to the target, or \(-1\) if no such path exists.

inputFormat

The first line contains two space-separated integers \(R\) and \(C\), the number of rows and columns.
The next \(R\) lines each contain \(C\) space-separated integers (0 or 1) representing the grid.
The following line contains two integers, the starting position \(s_r\) and \(s_c\).
The last line contains two integers, the target position \(t_r\) and \(t_c\).

outputFormat

Output a single integer representing the length of the shortest path. If the target cannot be reached, output -1.

5 5
0 0 1 0 0
1 0 1 1 1
0 0 0 0 1
1 1 1 0 0
0 0 1 0 0
0 0
4 4

8