#P4041. [Neerc2013]ASCII Puzzle

    ID: 3243 传统题 1000ms 128MiB 尝试: 6 已通过: 1 难度: 7 上传者: 标签>难度分类提高枚举与搜索Algorithm XDancing Links可行性剪枝搜索顺序优化CF2200

[Neerc2013]ASCII Puzzle

题目描述

Fili 沿格线把一张宽 WW、高 HH 的方格纸剪成 kk 块,并打乱各块的顺序。Floi 只能平移拼图块,不能旋转或翻转,要把它们拼回原来的方格纸。

给定每块对应的基准矩形宽度 ww 和高度 hh。设 k=n2k=n^2,则 W=nwW=nw、H=nhH=nh。把原方格纸分成 nn 行 nn 列 w×hw\times h 的基准矩形。一个合法切割须满足:

  1. 每块均为四连通且无洞的方格区域。原纸每个格恰好属于一块。
  2. 拼图块与基准矩形一一对应。每块必须包含对应基准矩形的四个角格。
  3. 每块的格子只能来自对应的基准矩形、与该矩形中的格子共边的格子、或与该矩形共边的其他基准矩形的内部格子。
  4. 相邻拼图块之间的切口不能是一条直线。

每块都能放在一个宽 3w−23w-2、高 3h−23h-2 的描述窗口里,对应的 w×hw\times h 基准矩形恰在窗口中央。

原题示意图:中央块和右上角块的允许格子

图中 W=12W=12、H=9H=9、w=4w=4、h=3h=3,虚线把原纸分成九个基准矩形。左图为中央块,右图为右上角块。黑色四格必须属于该块,灰色为其余允许格,粗实线为该块的描述窗口。

输入格式

第一行输入三个整数 k,w,hk,w,h。其中 k=n2k=n^2,1≤n≤41\le n\le4,3≤w,h≤53\le w,h\le5。

接下来依次描述 kk 个拼图块。每块占 3h−23h-2 行,每行恰有 3w−23w-2 个字符。块与块之间有一个空行。第 ii 块用英文字母表中的第 ii 个大写字母标记属于该块的格子,其他格子用英文句点 . 标记。保证输入来自一个合法切割。

输出格式

第一行输出两个整数 W,HW,H。随后输出 HH 行,每行 WW 个大写字母,表示拼好后每个格所属的拼图块。若有多个合法方案,输出任意一个。

样例 #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

NEERC 2013 原题 PDF(第 1–2 页)