Minimum Teleportations Required

You are given a grid of size (n \times m) where each cell is either a free cell (denoted by a dot '.') or an obstacle (denoted by a hash '#'). You start at the top-left cell ((0, 0)) and need to reach the bottom-right cell ((n-1, m-1)). You can move one step at a time in any of the four cardinal directions (up, down, left, right) provided that the destination cell is free. The grid is designed so that there exists a clear path between the start and the destination. Although the problem statement mentions teleportations, in every valid test case the grid allows a path without requiring any teleportation. Your task is to determine the minimum number of teleportations required. Under the given constraints, if there is a valid route, the answer will be (0). If no path exists (which will not occur in the test cases), output (-1).

inputFormat

The first line contains two integers (n) and (m), representing the number of rows and columns respectively. The following (n) lines each contain a string of length (m) which describes the grid.

outputFormat

Output a single integer which represents the minimum number of teleportations required to reach from the top-left corner to the bottom-right corner. Use standard input (stdin) and output (stdout).## sample

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

0