Minimum Steps in a Grid Maze

You are given a grid of size \(n \times m\) where each cell is either a free cell denoted by . or an obstacle denoted by #. Starting from the top-left cell (0-indexed) and moving to the bottom-right cell, your task is to compute the minimum number of steps required if you can move up, down, left, or right to an adjacent free cell.

If either the starting or the ending cell is blocked, or if there is no possible path, output \(-1\).

Note: The problem can be represented as finding the shortest path in an unweighted grid graph. Use Breadth-First Search (BFS) for an optimal solution.

inputFormat

The first line of input contains two integers \(n\) and \(m\) representing the number of rows and columns in the grid.

The following \(n\) lines each contain a string of length \(m\) consisting of characters . and # representing the grid.

outputFormat

Output a single integer representing the minimum number of steps required to reach the bottom‐right cell from the top‐left cell, or \(-1\) if such a path does not exist.

5 5
.....
.#.#.
.#.#.
.#.#.
.....

8