Minimum Steps to Reach Target

You are given a grid of size \(n \times m\) representing a game map. Each cell is either . (an open cell) or # (an obstacle). You are also given a starting position \((sx, sy)\) and a target position \((tx, ty)\) (1-indexed). Your task is to determine the minimum number of steps required to reach the target from the start. In one step, you can move to an adjacent cell (up, down, left or right) but you cannot move diagonally or step into a cell marked with an obstacle. If the target cannot be reached, output \(-1\).

Note: The grid positions and moves are described using standard Cartesian directions. The number of steps required may be computed using a breadth-first search (BFS) algorithm.

inputFormat

The input is provided via standard input (stdin) with the following format:

<n> <m>
<row1>
<row2>
...
<rown>
<sx> <sy> <tx> <ty>

\(n\) and \(m\) are the number of rows and columns respectively. Each of the next \(n\) lines contains a string of length \(m\) representing the grid row. Finally, the last line contains four integers: \(sx\), \(sy\), \(tx\), and \(ty\), where the positions are 1-indexed.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of steps required to reach the target cell from the starting cell. If there is no valid path, output \(-1\).

5 5
...#.
##.#.
.....
#.##.
.....
1 1 5 5

8