Minimum Obstacle Removal Path

You are given a grid with N rows and M columns. Each cell in the grid is either walkable, denoted by ., or blocked by an obstacle, denoted by #. Starting at the top‐left corner (0, 0) and aiming to reach the bottom‐right corner (N-1, M-1), your task is to determine the minimum number of obstacles that must be removed to form a valid path. However, you are allowed to remove at most \(K\) obstacles. Movement is restricted to only two directions: right and down.

If a valid path does not exist within the available obstacle removals, output \(-1\). Otherwise, output the minimum number of obstacles that need to be removed.

inputFormat

The input is given from standard input and has the following format:

N M K
row1
row2
...
rowN

Here, the first line contains three integers \( N \), \( M \), and \( K \), representing the number of rows, number of columns, and the maximum number of obstacles that can be removed, respectively. Each of the next \( N \) lines contains a string of length \( M \) consisting of characters . and # that represent the grid.

outputFormat

Output a single integer to standard output — the minimum number of obstacles that must be removed to reach the destination, or \(-1\) if it is impossible.

3 3 2
.#.
###
.#.

2