Maze Shortest Path Finder

You are given a maze represented by a grid of characters. Each cell in the maze is either . (an open path) or # (a wall). The maze is provided as R rows and C columns. You are also given the start and the end coordinates in the maze (0-indexed).

The task is to find the shortest path from the start cell to the end cell by moving only in the four cardinal directions (up, down, left, right). If a valid path exists, output the minimum number of steps required to reach the destination; if not, output NO PATH.

Note: If the start and end positions are the same, the required number of steps is 0.

Formally, if we let \(d(u,v)\) denote the minimum number of steps to travel from cell \(u\) to cell \(v\), your task is to compute and output \(d(\text{start}, \text{end})\) if it exists; otherwise, output "NO PATH".

inputFormat

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

R C
row1
row2
...
rowR
start_row start_col
end_row end_col

Where:

• R and C are the number of rows and columns in the maze.
• Each row is a string of length C consisting only of the characters . and #.
• start_row and start_col denote the starting cell (0-indexed).
• end_row and end_col denote the destination cell (0-indexed).

outputFormat

Output the minimum number of steps required to move from the start cell to the end cell. If no such path exists, output NO PATH.

The output should be written to standard output (stdout).

## sample

4 4
....
....
....
....
0 0
3 3

6