Shortest Path in a Grid

You are given a grid of size \(n \times m\) represented by n strings. Each string consists of characters '0' and '1', where '0' represents an open cell and '1' represents a wall. Your task is to compute the shortest path from the top-left cell \((0, 0)\) to the bottom-right cell \((n-1, m-1)\) by moving only in the four cardinal directions (up, down, left, right). The answer is defined as the minimum number of steps needed to reach the destination. It is guaranteed that there is always a valid path.

Note: The problem can be formalized as finding the smallest d such that there exists a sequence of moves from \((0,0)\) to \((n-1, m-1)\) while only stepping onto cells \(i,j\) where the corresponding character is '0'.

inputFormat

The input is given via standard input (stdin) and consists of:

• The first line contains two integers \(n\) and \(m\) separated by a space, representing the number of rows and columns of the grid.
• Each of the next \(n\) lines contains a string of length \(m\) composed of '0's and '1's, representing a row of the grid.

outputFormat

Output a single integer to standard output (stdout) which is the minimum number of steps required to go from the top-left cell to the bottom-right cell.

5 5
00000
01110
00000
01110
00000

8