Wall-Breaking Maze

Interview

Time limit1sMemory limit128 MB

Summary

Find the minimum number of walls to break on a grid path from the top-left to the bottom-right room, moving through 4 directions.

Level: Medium5 of 10
Topics: BFS, Shortest path, Matrix
Solved: No attempts yet

Problem

There is a maze with N rows and M columns. The maze consists of 1 * 1 rooms, and each room is either empty or a wall. You can move freely through empty rooms, but you can enter a wall room only after breaking that wall.

Several people are moving together, but they must always remain in the same room. If the current position is (x, y), they may move to one of the adjacent rooms (x + 1, y), (x - 1, y), (x, y + 1), or (x, y - 1). They cannot move outside the maze.

Once a wall is broken, that room becomes passable like an empty room.

Starting from (1, 1), find the minimum number of walls that must be broken to reach (N, M).

Input

The first line contains the width M and the height N of the maze. (1 <= N, M <= 100)

The next N lines describe the maze. Each line is a string of length M consisting of 0 and 1. 0 means an empty room, and 1 means a wall.

(1, 1) and (N, M) are always empty rooms.

Output

Print the minimum number of walls that must be broken to move from (1, 1) to (N, M).

Examples3

Example 1
Input
```
3 3
011
111
110
```
Expected output
```
3
```
Example 2
Input
```
4 2
0001
1000
```
Expected output
```
0
```

Example 3

Input

Expected output