Shortest Path in a Grid

You are given a grid of size \(n \times m\) consisting of characters "." and "#" where "." represents a walkable cell and "#" represents an obstacle. You are also given the starting point \((sx, sy)\) and the finishing point \((fx, fy)\). The grid positions are 1-indexed. Your task is to find the shortest distance from the starting cell to the finishing cell moving only in four directions: up, down, left, and right.

If there is no valid path between the two positions, output \(-1\). Note that if the starting point is the same as the finishing point, the distance is 0.

The shortest distance is defined as the minimum number of moves required to reach the finishing point from the starting point.

inputFormat

The input is given via standard input (stdin) and has the following format:

n m
row_1
row_2
... 
row_n
sx sy
fx fy

Where:

• \(n\) and \(m\) are integers representing the number of rows and columns of the grid.
• Each of the next \(n\) lines contains a string of length \(m\) consisting of characters "." and "#".
• \(sx\) and \(sy\) are the 1-indexed coordinates of the starting position.
• \(fx\) and \(fy\) are the 1-indexed coordinates of the finishing position.

outputFormat

Output a single integer to standard output (stdout): the length of the shortest path from \((sx, sy)\) to \((fx, fy)\). If there is no valid path, output \(-1\).

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

8