CF142C Help Caretaker

秋天迟迟来到遥远王国。丰收异常，现在到了为冬天做准备的时候。正当大多数人庆祝丰收节时，管理员 Simon 正在为农用设备在仓库中的存放问题而苦恼。 他的问题出在某种异常庞大的农具上，这些设备当然就是“turboplow”。问题在于 turboplow 存放时并不是简单地占据一个矩形空间，而是像下图四种形状之一那样，占据一个 T 形区域（其中 “#” 表示被 turboplow 占据的空间，“.” 表示空闲空间）： ``` ### ..# .#. #.. .#. ### .#. ### .#. ..# ### #.. ``` Simon 面临着一个很自然的挑战：在给定的 $n \times m$ 的仓库中，最多能放下多少台 turboplow。当你存放 turboplow 时，可以任选它四种朝向（即以上四种形状），但两台 turboplow 不能有任何“重叠”，即不能共用同一个仓库单元格。 Simon 觉得自己一个人无法找出能够最大化放置 turboplow 的最佳方案。你能帮帮他吗？

仅一行，包含两个用空格分隔的整数 $n$ 和 $m$，表示仓库的尺寸，$1 \leq n, m \leq 9$。

第一行输出仓库中最多能放多少台 turboplow。接下来 $n$ 行，每行输出 $m$ 个字符，用 “.”（点）表示空位置，用连续的大写英文字母（第 $1$ 个 turboplow 用 “A”，第 $2$ 个用 “B”，依次类推，直到方案中 turboplow 的数量）表示该 turboplow 所占据的空间。turbo plow 的编号顺序不限。对于同一尺寸的仓库，如果有多个最优方案，输出任意一个即可。

由 ChatGPT 5 翻译