Drone Navigation: Avoiding Buildings

You are given a grid representing a city where the drone must travel from a starting cell to a target cell. The grid is composed of . (open space) and # (building). The drone can only traverse cells that do not contain a building. Your task is to determine whether there exists a path from the start to the target that does not pass through any building cells.

If such a path exists, output 0 (indicating that the drone avoids any building cells). Otherwise, if no such path exists, output -1.

The movement is allowed in the four cardinal directions: up, down, left, and right.

Mathematically, if we denote the grid as a matrix \(G\) with \(N\) rows and \(M\) columns, and if the start cell is \((S_x, S_y)\) and the target cell is \((T_x, T_y)\), then the drone can move from cell \((x,y)\) to \((x+dx, y+dy)\) for \((dx,dy)\) in \(\{(-1,0), (1,0), (0,-1), (0,1)\}\), provided that the destination cell is within bounds and \(G[x+dx][y+dy] = \texttt{'.'}\).

inputFormat

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

1. The first line contains two integers \(N\) and \(M\), representing the number of rows and columns in the grid.
2. The second line contains four integers \(S_x\), \(S_y\), \(T_x\), and \(T_y\) representing the starting cell coordinates and the target cell coordinates, respectively. The top-left cell is considered as coordinate \((0, 0)\).
3. The following \(N\) lines each contain a string of length \(M\), representing a row of the grid. Each character is either . (open space) or # (building).

You may assume that \(1 \leq N, M \leq 1000\) and that the coordinates given are valid.

outputFormat

Output a single integer on standard output. If there exists a path from the starting cell to the target cell that avoids buildings, output 0. Otherwise, output -1.

5 5
0 0 4 4
.....
.#.#.
.#.#.
.#.#.
.....

0