Minimum Moves with Obstacle Jumps

You are given a grid with n rows and m columns, and an integer k representing the maximum number of obstacle jumps allowed. Each cell of the grid is either . (an open space) or # (an obstacle). Starting from the top-left corner (cell (1,1)) and aiming to reach the bottom-right corner (cell (n,m)), you may move up, down, left, or right. If you encounter an obstacle, you may choose to jump over it by spending one jump, provided you have not exceeded k obstacle jumps.

The task is to determine the minimum number of moves required to reach the destination. A move is defined as a single step in one of the four cardinal directions. If it is not possible to reach the destination under the given conditions, output -1.

Formally, given integers \(n\), \(m\), and \(k\) and a grid \(G\) of size \(n \times m\), you need to compute the minimum number of moves to go from \((1,1)\) to \((n,m)\) with at most \(k\) jumps, where each jump allows you to step into an obstacle cell. If there is no valid path, output \(-1\).

inputFormat

The input is read from standard input (stdin) in the following format:

 n m k
 row1
 row2
 ...
 row_n

Here, n, m, and k are integers. Each of the next n lines contains a string of length m representing a row of the grid. The character . denotes an open space and # denotes an obstacle.

outputFormat

The output is a single integer written to standard output (stdout): the minimum number of moves required to reach the bottom-right corner from the top-left corner; or -1 if there is no valid path.

5 5 1
..#..
#.#..
...#.
#.#.#
.....

8