Assume that you are given a two-dimensional grid \(G\) that contains \(N\) rows and \(M\) columns. The grid \(G\) consists of only three integers (\(0\), \(1\), and \(2\)).
- \(0\) denotes an empty cell
- \(1\) denotes that a cell contains a plant
- \(2\) denotes a cell where you are standing initially
You can move into an adjacent cell if that adjacent cell is empty. Two cells are adjacent if they share a side. In other words, if a cell is empty, then you can move in one of the four directions, Up, Down, Left, and Right.
You cannot move out of the grid \(G\).
Your task is to find the length of the shortest path to reach one of the boundary edges of the grid without stepping on a plant. The length of a path is equal to the number of moves you make.
Note: It is guaranteed that there is only one cell with value \(2\) (you are standing in only one cell initially).
Input format
- First line: Two space-separated integers, \(N\) and \(M\), denoting the number of rows and columns in the grid \(G\) respectively
- Next \(N\) lines: \(M\) space-separated integers denoting the rows of the grid \(G\)
Output format
Print the length of the shortest path to reach one of the boundary edges of the grid without stepping on a plant. If it is not possible to reach the edge of the grid, then print \(-1\).
Constraints
\(1 \le N, M \le 100\)
\(0 \le G_{i, j} \le 2\) where \(G_{i,j}\) denotes a cell of the \(G\) grid
There are 4 rows and 5 columns in the grid.
1 1 1 0 1
1 0 2 0 1
0 0 1 0 1
1 0 1 1 0
Initially, you are standing at cell \((2, 3)\) (second row and third column) denoted by 2. There are three ways to reach an boundary edge of the grid without stepping on a plant.
- Move to cell \((2, 2)\) (Left), then move to cell \((3, 2)\) (Down) and then move to cell \((4, 2)\) (Down) (3 steps).
- Move to cell \((2, 2)\) (Left), then move to cell \((3, 2)\) (Down) and then move to cell \((3, 1)\) (Left) (3 steps).
- Move to cell \((2, 4)\) (Right) and then move to cell \((1, 4)\) (Up) (2 steps).
In the third step, we took only 2 steps to reach to the edge of the grid which is the shortest path.
