Shortest Path in a Grid

You are given a grid of size \(n \times m\) consisting of characters '.' and '#'. A cell with '.' represents a traversable space, while '#' represents an obstacle. Your task is to find the shortest path from the top-left cell (0, 0) to the bottom-right cell (n-1, m-1) moving in the four cardinal directions (up, down, left, right). If a path exists, output the minimum number of steps required; if no such path exists or if the start or end cell is blocked, output -1.

Note: If the grid has only one cell, and that cell is traversable, the shortest path length is 0.

inputFormat

The first line contains two space-separated integers \(n\) and \(m\), representing the number of rows and columns respectively.

The following \(n\) lines each contain a string of exactly \(m\) characters. Each character is either '.' (free cell) or '#' (obstacle).

The input is provided via standard input (stdin).

outputFormat

Output a single integer — the minimum number of steps required to travel from the top-left cell (0, 0) to the bottom-right cell (n-1, m-1). If there is no valid path, output -1.

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

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

7