CF1771E Hossam and a Letter

Hossam 买了一块长为 $n$、宽为 $m$ 的新土地，他将其划分为一个 $n \times m$ 的网格，每个格子的大小为 $1\times1$。 由于 Hossam 的名字以字母 'H' 开头，他决定通过在土地上的某些格子上建造 $1\times1$ 的墙来绘制大写字母 'H'。每个 $1\times1$ 的格子都有一个质量等级：完美、中等或差。 建造墙体以形成字母 'H' 的过程有以下约束： - 字母必须由一条水平线和两条竖直线组成。 - 两条竖直线不能在同一列或相邻列。 - 两条竖直线必须从同一行开始，并在同一行结束（即长度相同）。 - 水平线应连接两条竖直线，但不能穿过它们。 - 水平线可以位于竖直线之间的任意一行（不一定在中间），但不能在最上面或最下面一行。（如果水平线在最上面一行，字母看起来像 'n'，如果在最下面一行，则像 'U'。） - 禁止在质量为差的格子上建造墙体。 - 最多只能使用一个中等质量的格子。 - 可以使用任意数量的完美质量格子。 请你求出绘制一个大写字母 'H' 所能使用的最大墙体数量。 如果无法绘制任何一个字母 'H'，请输出 $0$。

输入的第一行包含两个整数 $n$、$m$（$1 \le n, m \le 400$）。 接下来的 $n$ 行，每行包含 $m$ 个字符，描述了网格的情况。字符 '.' 表示完美格子，字符 'm' 表示中等格子，字符 '\#' 表示差格子。

输出一个整数，表示构成一个大写字母 'H' 所能使用的最大墙体数量。 如果无法绘制任何一个字母 'H'，输出 $0$。

在第一个测试用例中，无法绘制字母 'H'。 在第二个测试用例中，下图表示了网格以及一些合法的字母 'H'。完美、中等和差格子分别用白色、黄色和黑色表示。  由 ChatGPT 4.1 翻译