ジグソーパズル - Problem

牛たちは文字のジグソーパズルを始めました。$R$ 行（$(1 \le R \le 10)$）、$C$ 列（$(1 \le C \le 10)$）で、辺は変わった紙片の形ではなく文字です。

各ピースに番号と $4$ 個の文字または境界があり、通常のパズルのように揃えます。疑似文字 0（数字の零）は境界です。角や、例えば $4\times1$ の列の上端なら境界が複数あります。次の六ピースは多数ある完成方法の一つで、境界は 0 の代わりに線で示します。

              +---+  +---+  +---+
              | 1 c  c 3 d  d 5 |
              +-d-+  + a +  +-e-+

              +-d-+  +-a-+  +-e-+
              | 2 b  b 4 b  b 6 |
              +---+  +---+  +---+

隣接ピースの接する文字は一致し、境界は上下と側面に正しく現れます。

ピースは番号と時計回りの四辺で表し、辺は $a,\ldots,z$ の文字または 0。配置時に回転が必要かもしれません。

少なくとも一つ完成方法を求めてください。$R$、$C$ が大きいデータは辺の文字が多様なので解きやすくなっています。

第 $1,\ldots,R\times C$ 行：第 $R\times (i-1)+j$ 行は行 $i$、列 $j$ のピース。空白区切り五項で整数番号、上、右、下、左の辺識別子です。

2 3
1 c d 0 0
2 0 d b 0
3 c 0 d a
4 b a b 0
5 d 0 0 e
6 0 0 b e

1 0 c d 0
3 0 d a c
5 0 0 e d
2 d b 0 0
4 a b 0 b
6 e 0 0 b

入力はパズルを表し、一部ピースは出力例に対して回転しています。

本文の図のとおりです。反転など別の解も可能で、採点プログラムが検査します。

問題作成者：Rob Kolstad、2008

QOJ.ac