Minimum Moves to Treasure

You are given a grid representing a cave. The grid has n rows and m columns, where each cell is either a free cell denoted by . or an obstacle denoted by #. The treasure is located at the bottom-right cell \((n-1, m-1)\) and the entrance is at the top-left cell \((0,0)\). You can move in four directions: up, down, left, and right. Your task is to determine the minimum number of moves required to reach the treasure from the entrance, or output -1 if the treasure cannot be reached.

Note: The problem can be typically solved using a breadth-first search (BFS) algorithm. Make sure to consider the cases where either the entrance or the treasure is blocked by an obstacle.

inputFormat

The input is read from standard input (stdin) and has the following format:

 n m
 row_1
 row_2
 ...
 row_n

Where:

• n and m are integers representing the number of rows and columns respectively.
• Each row_i is a string of length m consisting of characters . (free cell) and # (obstacle).

The entrance is at \((0, 0)\) and the treasure is at \((n-1, m-1)\).

outputFormat

Output a single integer to standard output (stdout), which is the minimum number of moves required to reach the treasure from the entrance. If the treasure cannot be reached, output -1.

5 5
..#..
.#...
..#..
#....
...#.

8