Placing Two Crosses

Interview

Time limit2sMemory limit512 MB

Summary
Given a small grid of '.' and '#', place two non-overlapping crosses made of '#' cells and maximize the product of their areas.
Level

Medium5 of 10

Topics
Brute force, Implementation, Simulation, Array
Solved
No attempts yet

Problem

A cross has a '*' at its center and an equal length of '*' extending up, down, left, and right from the center. The size of a cross is the number of '*' extending in each of the four directions from the center. The size of a cross must be greater than or equal to 0.

The figure below shows crosses of size 0, 1, 2, and 3, where empty cells are '.'.

                  ...*...
          ..*..   ...*...
    .*.   ..*..   ...*...
*   ***   *****   *******
    .*.   ..*..   ...*...
          ..*..   ...*...
                  ...*...

The area of a cross is the number of '*' it contains. The areas of crosses of size 0, 1, 2, and 3 are 1, 5, 9, and 13.

A grid of size N×M consisting of '.' and '#' is given. You want to place two crosses on the grid so that they do not overlap. A cross can only be placed on cells containing '#'. Find the maximum possible product of the areas of the two placed crosses.

Input

The first line gives the dimensions of the grid, N and M (2 ≤ N, M ≤ 15). The next N lines give the state of the grid. The input is always given such that two crosses can be placed.

Output

On the first line, output the maximum possible product of the areas of the two placed crosses.

Examples2

  1. Example 1

    Input
    5 6
######
#...#.
######
##..#.
######
    Expected output
    5

  2. Example 2

    Input
    6 6
.#..#.
######
.#..#.
######
.#..#.
.#..#.
    Expected output
    25