A vault floor is a grid of R rows and C columns. Each cell is either open (.) or a wall (#). A robot starts at the top-left cell (0,0) and must reach the bottom-right cell (R-1, C-1), moving one cell at a time up, down, left, or right.
The robot may move freely into open cells, but to step onto a wall cell it must break that wall, at a cost of one. Entering an open cell costs nothing. The cost of a route is the total number of wall cells it steps onto (this includes the start and target cells themselves if they happen to be walls). Find the minimum total cost to get from the top-left to the bottom-right cell. It is guaranteed the grid is non-empty, so the two cells always exist (they may be the same cell).
Input format
Line 1: two integers R and C.
Each of the next R lines: a string of exactly C characters, each . or #.
Output format
A single integer: the minimum number of wall cells that must be broken to travel from (0,0) to (R-1, C-1).
Constraints
- 1 <= R, C <= 300
- Each grid character is
.or#.