← 返回题目列表

Codeforces · 142/C

C. 帮助管理员

中文机器翻译题面 查看原题

遥远王国的秋天来得很晚。庄稼丰收,现在是为过冬做准备的时候了。当大多数人庆祝丰收节时,看门人西蒙试图解决一项非常重要的任务:如何在仓库中为农业设备找到位置。

他在使用一些特别大的设备时遇到了问题,当然就是涡轮喷气机。问题是,当涡轮喷气机被存放时,它占用的不仅仅是一些简单的矩形空间。它占据了一个T形空间,如下四张图之一(这里字符“#”代表涡轮增压器占用的空间,字符“.”代表可用空间):

### ..# .#. #...#. ### .#. ###.#. ..# ### #..

Simon 面临着一个非常自然的挑战:在给定的 n × m 单元格仓库中放置最大数量的涡轮犁。当一个人存放涡轮犁时,他可以以任何方式旋转它们(以便它们占据像上面四张图片之一一样的空间)。然而,两台涡轮犁不能“重叠”,即它们不能共享仓库中的同一个单元。

Simon 认为他无法独自找到在仓库中放置插头的最佳方式,以最大限度地提高其数量。你能帮助他吗?

输入

唯一的一行包含两个空格分隔的整数 n 和 m — 仓库的大小 (1 ≤ n, m ≤ 9)。

输出

在第一行中打印可以放置在仓库中的涡轮犁的最大数量。在接下来的 n 行中,每一行打印 m 个字符。使用 ”。” (点)来标记空白空间,并使用连续的大写拉丁字母(“A”表示第一个涡轮犁,“B”表示第二个,依此类推,直到达到方案中的涡轮犁数量)来标记相应涡轮犁的位置,考虑到它们在仓库中的最佳位置。涡轮犁位置的编号顺序并不重要。如果对于给定大小的仓库有多个最佳解决方案,请打印其中任何一个。

示例

输入 #1

3 3

输出 #1

1
AAA
.A.
.A.

输入 #2

5 6

输出 #2

4
A..C..
AAAC..
ABCCCD
.B.DDD
BBB..D

输入 #3

2 2

输出 #3

0
..
..