Minimum Energy Path in a Grid

You are given an n x m grid representing a map. Each cell is either passable (represented by a '.') or an obstacle (represented by a '#'). You start at the top-left cell (1, 1) and your goal is to reach the bottom-right cell (n, m) by only moving up, down, left, or right. Moving to any adjacent passable cell costs 1 unit of energy.

The task is to compute the minimum energy required to reach (n, m) from (1, 1). If it is impossible to reach the destination, output -1.

In mathematical terms, if you let \(E\) denote the energy spent, then for every move into a passable cell, \(E\) increases by 1, i.e., \(E = E + 1\). You need to find the minimum \(E\) such that you can travel from the start to the destination.

Note: The starting cell and the destination cell must be passable; if either is an obstacle, the answer is -1.

inputFormat

The first line contains two integers n and m representing the number of rows and columns in the grid respectively.

The next n lines each contain a string of length m, representing the grid. Each character is either . (a passable cell) or # (an obstacle).

outputFormat

Output a single integer: the minimum energy (number of moves) required to reach the bottom-right cell from the top-left cell. If it is not possible, output -1.

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

7