Shortest Path in a Grid

You are given a grid with n rows and m columns. Each cell in the grid contains either 0 or 1, where 0 represents an open space and 1 represents an obstacle. Your task is to determine the shortest path from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,m)) by moving only in four directions (up, down, left, right). If the destination is unreachable or if the start or end cell is blocked, output -1.

Note: The number of moves is defined as the count of transitions between cells. If the start and destination are the same cell, the number of moves is 0.

The formula for Manhattan distance between two points \((x_1, y_1)\) and \((x_2, y_2)\) is given by:

inputFormat

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

1. The first line contains two integers n and m, representing the number of rows and columns respectively.
2. The next n lines each contain m space-separated integers (0 or 1) representing the grid.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of moves required to reach the bottom-right cell. If there is no valid path, output -1.

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 1 0
1 0 1 0 0
0 0 0 0 0

8