Shortest Path on a Grid

You are given an n x m grid representing a map. Each cell is either a clear cell (denoted by '.') or an obstacle/cloud (denoted by '#'). The goal is to compute the minimum number of moves required to travel from a starting coordinate to an ending coordinate. The telescope (or traveler) can move one cell at a time vertically or horizontally, but cannot pass through obstacles.

If the starting position is the same as the destination, the answer is 0. If there is no valid path, output -1.

The moves are defined such that each move from one cell to an adjacent cell has a cost of one. Formally, if the grid is represented by a matrix, and we denote the starting cell as \((sx, sy)\) and the ending cell as \((ex, ey)\), your task is to find the minimum distance \(d\) such that there exists a sequence of moves where each move is one of:

[ (sx, sy) \rightarrow (sx+1, sy), \quad (sx, sy) \rightarrow (sx-1, sy), \quad (sx, sy) \rightarrow (sx, sy+1), \quad (sx, sy) \rightarrow (sx, sy-1) ]

inputFormat

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

• The first line contains two integers \(n\) and \(m\) representing the number of rows and columns of the grid.
• The second line contains four integers: \(sx\), \(sy\), \(ex\), \(ey\) where \((sx, sy)\) is the starting coordinate and \((ex, ey)\) is the destination.
• The next \(n\) lines each contain a string of length \(m\), consisting only of the characters '.' and '#', representing the grid rows.

outputFormat

Output via stdout a single integer which is the minimum number of moves required to reach the destination. If there is no valid path, output -1.

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

8