Minimum Steps to Spread Rumor

You are given a grid with M rows and N columns. Each cell in the grid is either a junction point represented by . or an impassable area represented by #.

Your task is to determine the minimum number of steps required for a rumor to spread from a given starting junction at coordinates \((S_x,S_y)\) to a target junction at coordinates \((T_x,T_y)\). Movement is allowed only in the four cardinal directions: up, down, left, and right.

If the target junction is unreachable, output \(-1\).

This problem can be mathematically interpreted as finding the shortest path in a grid graph, where each valid move has a cost of 1.

inputFormat

The input is read from standard input with the following format:

1. The first line contains two integers (M) and (N), representing the number of rows and columns respectively.
2. The next (M) lines each contain a string of length (N), representing a row of the grid. Each character is either '.' (junction) or '#' (impassable area).
3. The following line contains two integers (S_x) and (S_y), the starting junction's coordinates (0-indexed).
4. The final line contains two integers (T_x) and (T_y), the target junction's coordinates (0-indexed).

outputFormat

Output a single integer: the minimum number of steps required for the rumor to reach the target junction via valid moves, or -1 if the target is unreachable.## sample

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

8