#P4041. [Neerc2013]ASCII Puzzle
[Neerc2013]ASCII Puzzle
题目描述
Fili 沿格线把一张宽 、高 的方格纸剪成 块,并打乱各块的顺序。Floi 只能平移拼图块,不能旋转或翻转,要把它们拼回原来的方格纸。
给定每块对应的基准矩形宽度 和高度 。设 ,则 、。把原方格纸分成 行 列 的基准矩形。一个合法切割须满足:
- 每块均为四连通且无洞的方格区域。原纸每个格恰好属于一块。
- 拼图块与基准矩形一一对应。每块必须包含对应基准矩形的四个角格。
- 每块的格子只能来自对应的基准矩形、与该矩形中的格子共边的格子、或与该矩形共边的其他基准矩形的内部格子。
- 相邻拼图块之间的切口不能是一条直线。
每块都能放在一个宽 、高 的描述窗口里,对应的 基准矩形恰在窗口中央。

图中 、、、,虚线把原纸分成九个基准矩形。左图为中央块,右图为右上角块。黑色四格必须属于该块,灰色为其余允许格,粗实线为该块的描述窗口。
输入格式
第一行输入三个整数 。其中 ,,。
接下来依次描述 个拼图块。每块占 行,每行恰有 个字符。块与块之间有一个空行。第 块用英文字母表中的第 个大写字母标记属于该块的格子,其他格子用英文句点 . 标记。保证输入来自一个合法切割。
输出格式
第一行输出两个整数 。随后输出 行,每行 个大写字母,表示拼好后每个格所属的拼图块。若有多个合法方案,输出任意一个。
样例 #1
样例输入 #1
4 4 3
..........
..........
...AAAA...
...AAAAAA.
...A.AA...
..........
..........
..........
..........
...BBBB...
.....BB...
...BBBB...
....BB....
.....B....
..........
..........
...C..C...
..CCC.C...
...CCCC...
..........
..........
..........
....D.....
...DDDD...
...DDD....
...DDDD...
..........
..........
样例输出 #1
8 6
AAAABBBB
AAAAAABB
ADAABBBB
DDDDCBBC
DDDCCCBC
DDDDCCCC