仓库源文，站点原文

title: "题解 - [Luogu P4205] [NOI2005] 智慧珠游戏" categories:

算法竞赛
题解 tags:
算法竞赛
题解
NOI
洛谷
DLX date: 2020-10-25 17:01:58

题目链接

原始题面

1000 ms / 125.00 MB

题目描述

智慧珠游戏拼盘由一个三角形盘件和 12 个形态各异的零件组成. 拼盘的盘件如图 1 所示:

12 个零件按珠子数分 3 大类:

第 1 大类, 有三个珠子, 只有一种形状
- 符号为 A, 形状为
第 2 大类, 有 4 个珠子, 有 3 种形状
- 符号为 B, 形状为
- 符号为 C, 形状为
- 符号为 D, 形状为
第 3 大类, 有 5 个珠子, 有 8 种形状
- 符号为 E, 形状为
- 符号为 F, 形状为
- 符号为 G, 形状为
- 符号为 H, 形状为
- 符号为 I, 形状为
- 符号为 J, 形状为
- 符号为 K, 形状为
- 符号为 L, 形状为

图 2 示出了一种拼盘方案. 为便于描述可将图 2 抽象为图 3, 就可以用一个数据为字符的二维数组来表示了

对于由珠子构成的零件, 可以放到盘件的任一位置, 条件是能有地方放, 且尺寸合适, 所有的零件都允许旋转(0º、90º、180º、270º)和翻转(水平、竖直)

现给出一个盘件的初始布局, 求一种可行的智慧珠摆放方案, 使所有的零件都能放进盘件中

输入输出格式

输入格式

文件中包含初始的盘件描述, 一共有 10 行, 第 i 行有 i 个字符. 如果第 i 行的第 j 个字符是字母"A"至"L"中的一个, 则表示第 i 行第 j 列的格子上已经放了零件, 零件的编号为对应的字母. 如果第 i 行的第 j 个字符是".", 则表示第 i 行第 j 列的格子上没有放零件. 输入保证预放的零件已摆放在盘件中

输出格式

如果能找到解, 向输出文件打印 10 行, 为放完全部 12 个零件后的布局. 其中, 第 i 行应包含 i 个字符, 第 i 行的第 j 个字符表示第 i 行第 j 列的格子上放的是哪个零件

如果无解, 输出单独的一个字符串'No solution'(不要引号, 请注意大小写)

所有的数据保证最多只有一组解

输入输出样例

输入样例 #1

.
..
...
....
.....
.....C
...CCC.
EEEHH...
E.HHH....
E.........

输出样例 #1

B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF

解题思路

把所有零件视作 4x4 且最上端无空行, 最左端无空列的图形, 之后把所有可能的图形预处理出来, 一共 60 种, 对这 60 种图形均尝试能否放入拼盘

状态这样选取:

单次操作为在某位置放某图形, 所以总的操作一共 $55\times 60=3300$ 种, 这其中有许多非法操作, 记得删掉
用 $55+12=67$ 维向量表示单次操作后的影响, 其中
- $1\sim 12$ 维表示放了某种零件
- $13\sim 67$ 维表示零件占据了哪些位置

参考代码里对拼盘和零件的编码方式如下:

Board::data[] 存储拼盘状态, 每 4 位表示一个格子, 第 r 行第 c 列 (从 0 开始) 格子的状态为 (Board::data[r] >> (4 * (9 - c))) & 15, 0 表示无珠子, f 表示不可放置

如第 4 行状态为 I.ADA 时, Board::data[4] 为 0x90141fffff
pieces[] 为所有零件对应的图形 (包含旋转和对称), 由 20 位构成, 其中高 4 位表示零件种类, 低 16 位为一个 4x4 图形

如 0x14c00 表示第 A 类零件, 用 x 表示有珠子, . 表示无珠子, 则图形为
```
.x..
xx..
....
....
```
零件对应图形的预处理代码参见命名空间 PieceOperation, 调用 PieceOperation::getall() 即可得到 pieces[]

代码参考

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb cpa_cpp title:Luogu_P4205 Luogu/P4205/0.cpp %} </details>