Minimum Number of Parks Required

You are given a city grid with R rows and C columns. Each cell in the grid is either a building, represented by the character 'B', or an empty space, represented by '.'. You can place a park in any cell. A park covers any building whose Manhattan distance from it is at most D.

The Manhattan distance between two cells at coordinates \((i_1,j_1)\) and \((i_2,j_2)\) is defined as \[ |i_1-i_2|+|j_1-j_2|, \] and is denoted in \(\LaTeX\) format above.

Your task is to determine the minimum number of parks needed so that every building in the grid is within a Manhattan distance of at most D from at least one park.

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains two integers R and C, representing the number of rows and columns of the grid respectively.
• The next R lines each contain a string of length C, representing a row of the grid. Each character is either 'B' (a building) or '.' (an empty space).
• The last line contains an integer D, representing the maximum allowed Manhattan distance from any building to a park.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of parks required.

4 5
.....
.....
.B...
.....
3

1