Zero-One Maze

Zero-One Maze

You are in an r x c grid, starting at the top-left cell and trying to reach the bottom-right ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌​‌​​‌‌​​‌‌​​‌‌​​‌‌​‌‌​​​‌‌​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​​​​​‌‌​​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌‌​​‌​​‌‌​‌‌​​​‌‌‌​​​​​‌‌‌​​‌​​‌‌‌​​​cell, moving up/down/left/right between orthogonally adjacent cells. Each cell is either open (.) or a wall (#). Moving into an open cell is free; moving into a wall cell costs 1 (you break through it, and it becomes passable). The start and end cells are always open. Find the ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌​‌​​‌‌​​‌‌​​‌‌​​‌‌​‌‌​​​‌‌​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​​​​​‌‌​​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌‌​​‌​​‌‌​‌‌​​​‌‌‌​​​​​‌‌‌​​‌​​‌‌‌​​​minimum total number of walls you must break to reach the end.

Input

Line 1: two integers r c (1 ≤ r, c ≤ 1000) Next r lines: a string of c characters, each . or #.

Output

A single integer: the minimum number of walls broken. ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌​‌​​‌‌​​‌‌​​‌‌​​‌‌​‌‌​​​‌‌​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​​​​​‌‌​​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌‌​​‌​​‌‌​‌‌​​​‌‌‌​​​​​‌‌‌​​‌​​‌‌‌​​​

Example

Input:

3 3
..#
.#.
#..

Output:

1

Constraints

• 1 ≤ r, c ≤ 1000 ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌​‌​​‌‌​​‌‌​​‌‌​​‌‌​‌‌​​​‌‌​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​​​​​‌‌​​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌‌​​‌​​‌‌​‌‌​​​‌‌‌​​​​​‌‌‌​​‌​​‌‌‌​​​

2 3
...
...

0

3 3
..#
.#.
#..

1