問題文
天下一程序员大赛的单色海报被高桥先生的恶作剧撕成了碎片。
海报是由H*W的正方形瓷砖组成,排列成H纵向W横向的矩形形状,但高桥君将其分解为四个T形块。
幸运的是,原始的数字数据仍然存在,但不幸的是我没有打印它的纸张。
你别无选择,只能修复这幅作品的海报。
入力
输入是按以下格式从标准输入给出的。
H W S_1 S_2 : : S_H N P_1 P_2 : : P_n
- 1 行中显示海报的垂直长度 H 和水平长度 W ( 4 \leq H,W \leq 12 )以整数形式给出,并用空格分隔。
- H, W 分别是 它总是能被 4 整除。
- 2 从行 H 行是代表原始海报的字符串 给出 S_i 。这个字符串是 W 字符。
- S_i 可以得到第j对于第一个字母,请单击左上角的图块。 (1,1) 坐标 表示 (j,i) 中图块的颜色。 “#”代表黑色瓷砖,“.”代表黑色瓷砖。代表白色瓷砖。
- H + 2 行显示件数。 N 。 表示
- H + 3 从行 N ( N = H * W / 4) 行表示给定块的图案类型。 给出了 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 的输入正确时,150 可以作为部分分数添加到完整分数。 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请注意,行尾需要换行。如果有多个答案,输出哪一个并不重要。
入力例 1
4 4 #... .#.. ..## ..## 4 9 6 1 8
出力例 1
1 4 3 1 1 0 4 1 1 4 4 2
- 可以恢复原始海报,如下图所示。
図 1:恢复海报
入力例 2
4 4 #... .#.. ..## ..## 4 1 2 3 4
出力例 2
-1
- 如果无法从给定的片段恢复原始海报,则输出-1。