Escape from grid

★★★★★

4.1

16 votes

Algorithms, Breadth First Search, Graphs, Medium

Details

Submissions

Discussion

Editorial

Problem

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

Sample Input

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

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.

Contributers:

Akash Sharma

Prateek Garg