Minimum Energy Path

You are given an N x M grid where each cell is either open ('.') or blocked ('#'). Your task is to determine the minimum energy required to move from the top-left cell (0, 0) to the bottom-right cell (N-1, M-1). You may move in four directions: up, down, left, and right. Each move costs 1 unit of energy.

If the destination is unreachable, output -1.

Note: The grid is provided as N lines, each containing a string of M characters. You are expected to use an algorithm such as breadth-first search (BFS) to compute the shortest path.

inputFormat

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

The first line contains two space-separated integers N and M, representing the number of rows and columns respectively. Each of the next N lines contains a string of length M representing a row of the grid.

outputFormat

Output a single integer to standard output (stdout) representing the minimum energy required to reach the bottom-right cell. Output -1 if it is impossible to reach the destination.## sample

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

6