Warehouse Shortest Path

Given a 2D grid (warehouse) consisting of cells, where each cell is either \(0\) (free space) or \(1\) (obstacle), determine the shortest path from a given start cell to a target cell. Movement is allowed in the four cardinal directions (up, down, left, right). The task is to find the minimum number of steps required to reach the target. If no valid path exists, output \(-1\).

The grid is represented as an \(m \times n\) matrix. Formally, if \(S=(s_x,s_y)\) is the starting cell and \(T=(t_x,t_y)\) is the target cell, you need to compute the minimum number of moves required such that:

[ \min { d \mid P(S,T,d) } , ]

where each move is a step to an adjacent cell (up, down, left, or right), and \(P(S,T,d)\) indicates that a path from \(S\) to \(T\) exists in \(d\) steps.

inputFormat

The input begins with two integers (m) and (n) representing the number of rows and columns of the grid respectively. This is followed by (m) lines, each containing (n) space-separated integers (each either 0 or 1) that describe the grid. The final line contains four integers: (s_x), (s_y), (t_x), and (t_y), representing the starting cell and the target cell respectively. The grid is zero-indexed.

outputFormat

Output a single integer: the minimum number of steps required to travel from the start cell to the target cell. If the target cannot be reached, output (-1).## sample

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

6