Taco: Minimum Moves to Reach Bottom-Right

You are given a grid with n rows and m columns. Each cell in the grid is either open ('.') or contains an obstacle ('#'). The robot starts at the top-left cell (position (0, 0)) and it wants to reach the bottom-right cell (position (n-1, m-1)). The robot can move one cell at a time in any of the four cardinal directions: up, down, left, or right.

Your task is to determine the minimum number of moves required for the robot to reach the bottom-right cell from the top-left cell. If reaching the destination is impossible, return \( -1 \).

Formally, let \( G[i][j] \) represent the cell in the grid. You need to find the smallest number of moves (steps) such that, starting from \( (0,0) \), you reach \( (n-1, m-1) \) only moving onto cells \( (i,j) \) where \( G[i][j] = '.' \). Moves are allowed only to adjacent cells in the four main directions.

inputFormat

The first line contains two integers, \( n \) and \( m \), representing the number of rows and columns of the grid, respectively. The following \( n \) lines each contain a string of length \( m \) representing one row of the grid. Each character is either a dot ('.') representing an open cell, or a hash ('#') representing an obstacle.

outputFormat

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

3 3
..#
.#.
...

4