A warehouse floor is a grid of R rows and C columns. Each cell is open aisle (.) or a shelf (#). A robot starts at the top-left cell (0,0) and wants to reach the bottom-right cell (R-1,C-1), moving one step at a time up, down, left, or right (never diagonally, never off the grid). Both the start and the goal are open aisle.
The robot carries a tool that lets it break through at most K shelves over the whole journey: it may step onto a shelf cell, but doing so uses up one of its K breaks. Stepping onto an open cell uses no break. Every step (onto an aisle or a broken shelf) counts as one move.
Report the minimum number of moves to reach the goal, or -1 if it cannot be reached even after breaking up to K shelves.
Input format
Line 1: three integers R, C, and K.
Next R lines: a string of exactly C characters, each . (aisle) or # (shelf). Cells and are always .
Output format
A single integer: the minimum number of moves, or -1 if unreachable.
Constraints
- 1 <= R, C <= 500
- 0 <= K <= R * C
- Every grid character is
.or#.