Minimum Moves in a Grid

You are given a grid with H rows and W columns. Each cell of the grid is either empty (represented by a '.') or an obstacle (represented by a '#'). Your task is to determine the minimum number of moves required to go from the top-left corner (cell (1,1)) to the bottom-right corner (cell (H,W)) if you can only move up, down, left, or right.

If either the starting or ending cell is blocked, or if there is no valid path between them, output -1.

The moves count is defined as the number of steps taken from one cell to an adjacent cell.

Formally, if we denote the grid as \(G\) where \(G_{i,j}\) is either \('.'\) or \('#'\), then the goal is to find the shortest path from \(G_{1,1}\) to \(G_{H,W}\) avoiding obstacles. Movement is allowed in four directions: up, down, left, and right.

Note: The input is taken from stdin and the result should be printed to stdout.

inputFormat

The first line contains two integers \(H\) and \(W\), indicating the number of rows and columns of the grid respectively.

The next \(H\) lines each contain a string of length \(W\) consisting of characters '.' and '#', representing the grid.

outputFormat

Print a single integer representing the minimum number of moves required to travel from the top-left to the bottom-right corner. If it is impossible, print -1.

## sample

4 4
....
.#..
....
....

6

</p>