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.)
Line 1: two integers R and C.
Next R lines: each contains C space-separated integers, each 0 (open) or 1 (wall).
A single integer: the minimum number of wall cells that must be broken on a best route.
Example 1
Input
3 3 0 0 0 1 1 0 0 0 0
Expected
0
Explanation
A route down the right column and across the bottom avoids every wall, so 0 breaks are needed.
Example 2
Input
3 3 0 1 0 0 1 0 0 1 0
Expected
1
Explanation
The middle column is a solid wall, so any route from left to right must break exactly one wall cell: 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →