A courier robot crosses an R-by-C grid from the top-left cell (0,0) to the bottom-right cell (R-1,C-1), moving one step at a time up, down, left, or right. Each cell is either open (0) or a wall (1).
The robot may pass through walls, but every wall cell it stands on (including the start or end cell, if they happen to be walls) costs one "break." Open cells are free to enter.
Find the minimum total number of breaks over all possible routes from start to end. (The robot can always reach the end by breaking through enough walls, so an answer always exists.)
Input format
Line 1: two integers R and C.
Next R lines: each contains C space-separated integers, each 0 (open) or 1 (wall).
Output format
A single integer: the minimum number of wall cells that must be broken on a best route.
Constraints
- 1 <= R, C <= 200
- Each cell is 0 or 1.