Minimum Steps in a Grid

You are given an n x m grid consisting of characters '.' and '#'. The character '.' denotes an open cell and '#' denotes an obstacle. Your task is to determine the minimum number of steps required to travel from the top-left cell (0, 0) to the bottom-right cell (n-1, m-1) by moving one cell at a time in one of the four cardinal directions (up, down, left, right). If there is no valid path, output -1.

The problem is a classic shortest path search in a grid with obstacles and can be solved using BFS. A step is defined as a movement from one cell to an adjacent cell.

Note: The starting cell or ending cell might be blocked.

inputFormat

The first line contains two space-separated integers n and m, representing the number of rows and columns. The following n lines each contain a string of length m, representing the grid. The character '.' denotes an open cell and '#' denotes an obstacle.

outputFormat

Output a single integer representing the minimum number of steps to reach the bottom-right cell from the top-left cell. If no path exists, output -1.## sample

3 3
...
.#.
...

4