Shortest Path in a Grid

You are given a grid representing a city. Each cell in the grid is either 0 or 1. A cell with 0 represents an empty space where you can walk, while a cell with 1 represents an obstacle (building) that you cannot pass through. Your task is to find the shortest path from a given start cell to a destination cell. Movements are allowed only in the four cardinal directions (up, down, left, right). If there is no possible path, output -1.

Note: The path length is defined as the number of moves from the start cell to the destination cell.

The problem can be mathematically described using the following concept:

Find the minimum d such that \[ \begin{aligned} & (x_0, y_0) = (\text{start_x}, \text{start_y}), \\ & (x_d, y_d) = (\text{dest_x}, \text{dest_y}), \\ & (x_{i+1}, y_{i+1}) \text{ is adjacent to } (x_i, y_i) \text{ and } \text{grid}[x_i][y_i] = 0, \quad \forall\, 0 \le i < d. \end{aligned} \] If such a sequence does not exist, output -1.

inputFormat

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

n m
row1
row2
... 
rown
start_x start_y dest_x dest_y

Here, n and m are positive integers representing the number of rows and columns of the grid respectively. Each of the next n lines contains a string of 0 and 1 characters representing the grid. The last line contains four integers specifying the starting cell coordinates (start_x, start_y) and the destination cell coordinates (dest_x, dest_y). The grid is zero-indexed.

outputFormat

The output should be written to stdout. Output a single integer: the length of the shortest path from the start cell to the destination cell, or -1 if no such path exists.

5 5
01000
01011
00000
11110
11111
0 0 4 4

-1