Wall-Breaking Maze

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).

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.

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