Hossam and a Letter
Contest: Codeforces Round 837 (Div. 2)
Difficulty rating: 2500
Tags: brute force, dp, implementation, two pointers

Hossam bought a new piece of ground with length $$$n$$$ and width $$$m$$$, he divided it into an $$$n \cdot m$$$ grid, each cell being of size $$$1\times1$$$.

Since Hossam's name starts with the letter 'H', he decided to draw the capital letter 'H' by building walls of size $$$1\times1$$$ on some squares of the ground. Each square $$$1\times1$$$ on the ground is assigned a quality degree: perfect, medium, or bad.

The process of building walls to form up letter 'H' has the following constraints:

- The letter must consist of one horizontal and two vertical lines.
- The vertical lines must not be in the same or neighboring columns.
- The vertical lines must start in the same row and end in the same row (and thus have the same length).
- The horizontal line should connect the vertical lines, but must not cross them.
- The horizontal line can be in any row between the vertical lines (not only in the middle), except the top and the bottom one. (With the horizontal line in the top row the letter looks like 'n', and in the bottom row like 'U'.)
- It is forbidden to build walls in cells of bad quality.
- You can use at most one square of medium quality.
- You can use any number of squares of perfect quality.

Find the maximum number of walls that can be used to draw the letter 'H'.

Check the note for more clarification.

Input format:
The first line of the input contains two integer numbers $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 400$$$).

The next $$$n$$$ lines of the input contain $$$m$$$ characters each, describing the grid. The character '.' stands for a perfect square, the character 'm' stands for a medium square, and the character '#' stands for a bad square.

Output format:
Print a single integer — the maximum number of walls that form a capital letter 'H'.

If it is not possible to draw any letter 'H', print $$$0$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can't build the letter 'H'.

For the second test case, the figure below represents the grid and some of the valid letters 'H'. Perfect, medium, and bad squares are represented with white, yellow, and black colors respectively.

Example input:
2 3
#m.
.#.

Example output:
0

Example input:
7 8
...#.m..
..m...m.
.#..#.m#
...m..m.
m.......
..#.m.mm
......m.

Example output:
16

Editorial:
Let's preprocess the following data for each cell.
1. first medium cell above current cell. 2. first medium cell below current cell. 3. first bad cell above current cell. 4. first bad cell below current cell.
Then we will try to solve the problem for each row (i), and 2 columns (j, k).
Now we have a horizontal line in row (i), and we can calculate the length of vertical line by the following.
There is two cases:
In case of the horizontal line contains one letter 'm'.
For each column (j, k): get first cell above it the don't contain ('#' or 'm') and first cell below it the don't contain ('#' or 'm').
In case of the horizontal line doesn't contain any letter 'm'.
We will try to get the 4 cells as it contains letter 'm', but in this case we will 4 trials.
for each cell from the 4 cells, we allow to have only one letter 'm' in that line.
After getting above cells and below cells for each line. the starting cell will be the maximum between the two above cells, and the ending cell will be the minimum between the two below cells.
Then we need to check that starting cell is above the current row (i) to avoid making letter n instead of H
And check that ending cell is below the current row (i) to avoid making letter u instead of H.
Since n, m has the same maximum limit 400.
Thus, time complexity of this solution is $$$O(n^3)$$$.