Robot Pathfinding: Minimum Steps

You are given a grid of size \(N \times M\) where each cell is either . (an open cell) or # (a blocked cell). The task is to determine the minimum number of steps required for a robot starting at the top-left corner (cell \((1,1)\)) to reach the bottom-right corner (cell \((N,M)\)). The robot can only move in the four cardinal directions: up, down, left, or right. If either the starting or ending cell is blocked, or if there is no valid path between them, the answer should be \(-1\). Note that if the grid consists of a single cell, the answer is \(0\) since the robot is already at the destination.

Movement Directions: The allowed moves from a cell \((i,j)\) are to the cells \((i+1,j)\), \((i-1,j)\), \((i,j+1)\), and \((i,j-1)\) provided that they are within the grid boundaries and not blocked.

inputFormat

The input is provided via standard input (stdin) and has the following format:

N M
row1
row2
...
rowN

Here, 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\) consisting of characters . and # which represent open and blocked cells respectively.

outputFormat

The output should be printed to standard output (stdout) as a single integer: the minimum number of steps required for the robot to move from the top-left to the bottom-right cell. If the destination cannot be reached, print \(-1\).

5 6
....#.
.#..#.
.#...#
#..#..
......

9