#K74097. Maximum Contiguous Black Block
Maximum Contiguous Black Block
Maximum Contiguous Black Block
Given a grid with R rows and C columns where each cell is either white (denoted by .
) or black (denoted by #
), you are allowed to repaint cells to black. The twist is that if there is at least one originally black cell in the grid, by repainting you can change all cells to black, thereby forming a contiguous block whose area is R × C.
However, if the grid does not contain any black cell initially (i.e. all cells are white), you are permitted to repaint one cell to black, yielding an area of 1. In summary, the answer is:
- If the grid contains at least one '#' then the maximum contiguous black block area is R × C.
- If the grid is entirely '.', then the answer is 1 (which is also R × C when R = C = 1).
Note: Since even an all-white grid of size larger than 1 would have R × C > 1, the intended interpretation of the problem is that any valid grid (even if initially all white) should be repainted fully if possible. Thus, for every test case the answer is effectively R × C.
This problem may seem trivial once the observation is made. In a competitive programming contest, carefully reading the problem statement and understanding the repainting operation is key.
inputFormat
The input is given via standard input. The first line contains two integers R and C representing the number of rows and columns respectively. This is followed by R lines, each containing a string of length C composed of the characters .
and #
, which represent white and black cells respectively.
Example:
4 5 .#... ..#.. ..#.. .....
outputFormat
Output a single integer to standard output, which represents the maximum area of a contiguous block of black cells that can be obtained after repainting the grid according to the aforementioned rules.
Example:
20## sample
4 5
.#...
..#..
..#..
.....
20