← 返回题目列表

AtCoder · tenka1_2013_qualA_e

E. 天海一拼图

中文机器翻译题面 查看原题

問題文

天下一程序员大赛的单色海报被高桥先生的恶作剧撕成了碎片。
海报是由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。