AT_tenka1_2013_qualA_e 天下一ジグソーパズル
题目描述
天下一程序员竞赛的黑白海报被高桥君恶作剧地拆散了。
海报原本是由 $H \times W$ 个正方形瓷砖，按 $H$ 行 $W$ 列排成的长方形组成的，但被高桥君拆解成了全部由 4 个瓷砖组成的“ト”字型拼块。
幸运的是，原始的数字数据还保留着，但遗憾的是，没有多余的纸张可以重新打印。
无奈之下，你需要用这些拼块来修复海报。
输入以如下格式从标准输入给出。
> 第 $1$ 行给出海报的高度 $H$ 和宽度 $W$（$4 \leq H,W \leq 12$），以空格分隔，均为整数。
> $H$ 和 $W$ 都能被 $4$ 整除。
> 第 $2$ 行到第 $H+1$ 行，每行给出一个长度为 $W$ 的字符串 $S_i$，表示原始海报。字符串的第 $j$ 个字符表示左上角为 $(1,1)$ 的坐标 $(j,i)$ 处瓷砖的颜色。'#' 表示黑色瓷砖，'.' 表示白色瓷砖。
> 第 $H+2$ 行给出拼块的数量 $N$。
> 第 $H+3$ 行到第 $H+2+N$ 行，每行给出一个整数 $P_i$（$1 \leq P_i \leq 16$），表示给定的拼块图案类型。拼块类型共有如下 16 种：
```
. # . # . # . # . # . # . # . #
.. .. #. #. .# .# ## ## .. .. #. #. .# .# ## ##
. . . . . . . . # # # # # # # #
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
```
- 若 $H,W \leq 4$ 的输入正确，将获得满分 $150$ 分中的 $30$ 分。
- 若 $H,W \leq 8$ 的输入正确，将额外获得 $50$ 分。
请输出 $n$ 行，描述修复拼图的方法。如果无法还原海报，则输出 -1。
第 $i$ 行请输出 $P_i$ 应放置的 $X$ 坐标、$Y$ 坐标、旋转方向，三者以空格分隔。旋转方向如图所示，左上角坐标为 $(1,1)$，输出的是下图中 A 位置的坐标。
```
A DBA D
BC C CB C
D A ABD
0 1 2 3
```
每行末尾需换行。如果有多种答案，输出任意一种均可。
例如：
```
4 4
#...
.#..
..##
..##
4
9
6
1
8
```
输出：
```
1 4 3
1 1 0
4 1 1
4 4 2
```
如图所示，可以还原原始海报。
 图 1：还原后的海报
再如：
```
4 4
#...
.#..
..##
..##
4
1
2
3
4
```
输出：
```
-1
```
若无法用给定拼块还原原始海报，则输出 -1。
输入格式
第 1 行：两个整数 $H$ 和 $W$，以空格分隔。
第 2 行到第 $H+1$ 行：每行一个长度为 $W$ 的字符串 $S_i$，表示原始海报。
第 $H+2$ 行：一个整数 $N$。
第 $H+3$ 行到第 $H+2+N$ 行：每行一个整数 $P_i$，表示拼块的类型。
输出格式
如果可以还原海报，则输出 $N$ 行，每行三个整数 $X\ Y\ R$，分别表示第 $i$ 个拼块的左上角坐标 $(X,Y)$ 和旋转方向 $R$（$0$ 到 $3$，顺时针旋转 $90$ 度的次数），以空格分隔。
如果无法还原，则输出 -1。
说明/提示
- $H$ 和 $W$ 均为 $4$ 的倍数。
- $1 \leq H,W \leq 12$。
- $N = H \times W / 4$。
- 拼块的类型和旋转方式如题面所示。
- 若有多种答案，输出任意一种均可。
- 若无法还原，输出 -1。
由 ChatGPT 4.1 翻译