Shortest Path in a Grid

Given an \(N \times N\) grid where each cell is either empty (represented by a .) or blocked (represented by a #), your task is to determine the shortest path from the top-left cell (position \((0, 0)\)) to the bottom-right cell (position \((N-1, N-1)\)). You may only move in the four cardinal directions: up, down, left, and right. Diagonal moves are not allowed.

Each move from one cell to an adjacent cell counts as one step. If a path exists, output the minimum number of steps required; otherwise, output \(-1\). For instance, the Manhattan distance between two cells \((x_1, y_1)\) and \((x_2, y_2)\) is given by \( |x_1 - x_2| + |y_1 - y_2| \), which is the lower bound on the number of steps in an open grid without obstacles.

inputFormat

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

• The first line contains an integer \(N\), the size of the grid.
• The next \(N\) lines each contain a string of length \(N\) representing a row of the grid. Each character is either a . (empty cell) or a # (blocked cell).

outputFormat

Output a single integer to standard output (stdout): the length of the shortest path from the top-left cell to the bottom-right cell. If no such path exists, output \(-1\).

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

8