Minimum Moves to Reach Goal with Adversarial Obstacles

Alice is trapped in a grid of size \(n \times m\) where some cells are already blocked and others are free. She starts from the upper-left cell (cell (1,1)) and wants to reach the bottom-right cell (cell (n,m)) in the minimum number of moves. However, Bob, who is against her, can place up to \(k\) additional obstacles in free cells (except the start and goal cells) after Alice’s initially computed shortest path (using a breadth-first search) is determined.

The grid is represented as a 2D board where a '.' (dot) denotes an empty cell and a '#' (hash) denotes an obstacle. Bob places obstacles by scanning the grid in row-major order and converting up to \(k\) free cells to obstacles. After Bob’s modifications, Alice must try to find a valid path again. Your task is to compute the minimum number of moves Alice can take to reach her goal after Bob places his obstacles optimally. If no path exists, output \(-1\).

Note: Moves are allowed in the four cardinal directions (up, down, left, right) and each move counts as one step. The start position is \((1,1)\) and the destination is \((n,m)\).

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\), representing the number of rows, columns, and the maximum number of obstacles Bob can place, respectively.

Each of the next \(n\) lines contains a string of length \(m\) consisting of characters '.' and '#' (without spaces) that represent the grid. The character '.' indicates an empty cell, and '#' indicates an already blocked cell.

outputFormat

Output a single integer representing the minimum number of moves required for Alice to reach the goal from the start after Bob places obstacles. If it is impossible for Alice to reach the goal, output \(-1\).

4 4 2
....
....
....
....

6