#K34547. Maximum Rectangular Billboard
Maximum Rectangular Billboard
Maximum Rectangular Billboard
You are given a plot of land represented as a grid of characters where each cell is either available ('.') or blocked ('#'). Your task is to compute the area of the largest possible rectangular billboard that can be placed on the available land. The billboard must be placed so that its sides are parallel to the grid.
Note: A cell with '.' is free and can be used to build part of the billboard while a '#' cell represents an obstacle.
The problem can be formulated as follows: Given a grid with n rows and m columns, find the maximum area of a rectangle consisting entirely of '.' characters. The area of a rectangle is given by (\text{Area} = \text{width} \times \text{height}).
inputFormat
The input is read from standard input (stdin). The first line contains two integers: n and m where n is the number of rows and m is the number of columns of the grid. This is followed by n lines, each containing a string of length m, representing the grid. Each character is either a '.' (free cell) or a '#' (obstacle).
outputFormat
Output a single integer to standard output (stdout) representing the area of the largest rectangle that can be obtained using only the '.' cells.## sample
4 5
....#
.#...
.#...
..#..
6