Codeforces Round 837 (Div. 2) |
---|
Finished |
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:
Find the maximum number of walls that can be used to draw the letter 'H'.
Check the note for more clarification.
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.
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$$$.
2 3 #m. .#.
0
7 8 ...#.m.. ..m...m. .#..#.m# ...m..m. m....... ..#.m.mm ......m.
16
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.
Name |
---|