Shortest Path in a Maze

Given a maze of size n x m where each cell is either open (denoted by '.') or blocked (denoted by '#'), determine the length of the shortest path from a starting cell to an ending cell. You are allowed to move only up, down, left, or right.

The starting cell is given as \((sx, sy)\) and the ending cell as \((ex, ey)\). The length of the path is defined as the number of moves from the starting cell to the ending cell. If no such path exists, output -1.

A typical way to solve this problem is by using the Breadth-First Search (BFS) algorithm which guarantees finding the shortest path in an unweighted grid.

inputFormat

The input is read via standard input (stdin) in the following format:

n m
maze_row_1
maze_row_2
... (n rows in total)
sx sy ex ey

Where:

• n and m are the number of rows and columns in the maze, respectively.
• Each maze_row is a string of exactly m characters ('.' for free cell and '#' for wall).
• sx, sy, ex, ey are integers that denote the starting and ending cell coordinates (0-indexed).

outputFormat

Output a single integer to standard output (stdout) representing the length of the shortest path from the start to the end. If there is no valid path, output -1.

3 3
...
...
...
0 0 2 2

4