天下一プログラマーコンテスト2013予選A

E - 天下一ジグソーパズル


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 64MB


問題文

天下一プログラマーコンテストのモノクロポスターが、高橋君のいたずらにより、バラバラにされてしまいました。
ポスターは、H*W個の正方形のタイルを、縦H個、横W個の長方形に敷き詰めて構成されていたのですが、高橋君によって、全てタイル4つで構成される、トの字型のピースに分解されてしまっています。
幸運なことに、元のデジタルデータは残っていましたが、残念なことに、印刷するための紙がありません。
仕方がないので、あなたはこのピースから、ポスターを修復しなければいけません。


入力

入力は以下の形式で標準入力から与えられる。

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座標、回転方向の3つの整数をスペース区切りで出力してください。 なお、回転方向は、下図のように時計回りに表し、ポスターの左上の座標を(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を出力する。

Submit提出する