Maze Search

Interview

Time limit1sMemory limit192 MB

Summary

Find the minimum number of cells traversed on a grid path from top-left to bottom-right using BFS shortest path.

Level: Easy3 of 10
Topics: BFS, Graph, Matrix
Solved: No attempts yet

Problem

You are given a maze with N rows and M columns. Each cell contains either 1 or 0. A cell with 1 can be entered, and a cell with 0 cannot be entered.

Starting from position (1, 1), find the minimum number of cells that must be passed through to reach position (N, M). You may move only to an adjacent cell sharing an edge. The starting cell and the destination cell are both included in the count.

Input

The first line contains two integers N and M (2 <= N, M <= 100). Each of the next N lines contains M digits describing the maze. The digits are given without spaces.

Output

Print the minimum number of cells that must be passed through. The input is guaranteed to contain at least one path to the destination.

Examples4

Example 1
Input
```
4 6
101111
101010
101011
111011
```
Expected output
```
15
```
Example 2
Input
```
4 6
110110
110110
111111
111101
```
Expected output
```
9
```

Example 3

Input

2 25
1011101110111011101110111
1110111011101110111011101

Expected output

Example 4

Input

Expected output