Hossam and a Letter

题意翻译

给定一个仅包含 `#`、`.`、`m` 的 $n$ 行 $m$ 列的矩阵，你需要找到一些能组成 `H` 的格子。这个 `H` 需满足以下要求： - 由两条竖直的线段和一条水平的线段组成。 - 两条竖直的线段由同一行开始，在同一行结束，且不能在同一列或相邻列。 - 水平的线段将两条竖直线段相连，但不在竖直线段的最后一行或第一行。注意水平的线段不能跨越竖直的线段。 - 不得包含 `#`，最多包含一个 `m`。 在满足条件的 `H` 中，找到所占格子数量最多的那个。输出其所占格子的数量。不存在输出 $0$。 $1\leq n,m \leq 400$。 Translated by @[StayAlone](https://www.luogu.com.cn/user/409236)

题目描述

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.

输入输出格式

输入格式

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 $ .

输入输出样例

输入样例 #1

2 3
#m.
.#.

输出样例 #1

0

输入样例 #2

7 8
...#.m..
..m...m.
.#..#.m#
...m..m.
m.......
..#.m.mm
......m.

输出样例 #2

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. 

**题目大意**：

给定一个仅包含 `#`、`.`、`m` 的 $n$ 行 $m$ 列的矩阵，需要找到一些能组成 `H` 的格子。这个 `H` 需满足以下要求：

- 由两条竖直的线段和一条水平的线段组成。
- 两条竖直的线段由同一行开始，在同一行结束，且不能在同一列或相邻列。
- 水平的线段将两条竖直线段相连，但不在竖直线段的最后一行或第一行。注意水平的线段不能跨越竖直的线段。
- 不得包含 `#`，最多包含一个 `m`。

在满足条件的 `H` 中，找到所占格子数量最多的那个。输出其所占格子的数量。不存在输出 $0$。

$1\leq n,m \leq 400$。

**输入输出格式**：

**输入格式**：

第一行包含两个整数 $ n $, $ m $ ($ 1 \le n, m \le 400 $)。

接下来的 $ n $ 行每行包含 $ m $ 个字符，描述矩阵。字符 `.` 表示完美方块，字符 `m` 表示中等方块，字符 `#` 表示坏方块。

**输出格式**：

打印一个整数——可以用来构成大写字母 `H` 的墙壁的最大数量。

如果无法绘制任何字母 `H`，则打印 $0$。**题目大意**： 给定一个仅包含 `#`、`.`、`m` 的 $n$ 行 $m$ 列的矩阵，需要找到一些能组成 `H` 的格子。这个 `H` 需满足以下要求： - 由两条竖直的线段和一条水平的线段组成。 - 两条竖直的线段由同一行开始，在同一行结束，且不能在同一列或相邻列。 - 水平的线段将两条竖直线段相连，但不在竖直线段的最后一行或第一行。注意水平的线段不能跨越竖直的线段。 - 不得包含 `#`，最多包含一个 `m`。 在满足条件的 `H` 中，找到所占格子数量最多的那个。输出其所占格子的数量。不存在输出 $0$。 $1\leq n,m \leq 400$。 **输入输出格式**： **输入格式**： 第一行包含两个整数 $ n $, $ m $ ($ 1 \le n, m \le 400 $)。 接下来的 $ n $ 行每行包含 $ m $ 个字符，描述矩阵。字符 `.` 表示完美方块，字符 `m` 表示中等方块，字符 `#` 表示坏方块。 **输出格式**： 打印一个整数——可以用来构成大写字母 `H` 的墙壁的最大数量。 如果无法绘制任何字母 `H`，则打印 $0$。