D - 天下一芸術
Editorial
/ 
/ 
Time Limit: 3 sec / Memory Limit: 256 MB
問題文
天下一王国の姫の命令で、画家でもあるトモアキ君は長方形の壁画を描くことになりました。
しかし、この仕事には困ったことが2つあります。
-
壁画を描くのに使う塗料は、姫に指定されたペンキを使わなければなりません。
- 姫に指定されたペンキはすべて異なる色です。塗った領域がそれぞれ異なる色で彩色されます。
- 各ペンキには「濃さ」があります。そのペンキよりも「濃さ」の値が低いペンキに対しては上から重ね塗りをして、そのペンキの色で上書きすることができますが、値が同じか高いペンキに対して上から重ね塗りをしてはいけません。
-
トモアキ君は天下一の不器用です。
- トモアキ君は、壁画の縦横に対して各辺が平行な長方形しか塗ることはできません。
- 1度使った色のペンキを2度使うことはできません。
トモアキ君は、なんとか壁画を完成させるためにまず壁画の設計図を作りました。
この設計図は、サイズ 1 \times 1 のマス目に分割されており各マスに番号が指定されています。
- 各マスの番号は色分けの指定をするものです。同じ番号のマスは同じ色になるように、異なる番号のマスは異なる色になるように塗られていなくてはいけません。
- マスの番号とペンキは任意の組み合わせで構いません。
- すべてのペンキを使用しなくても構いません。
- すべてのマスは、ペンキで1回以上塗らなくてはいけません。
壁画の制作を失敗できないトモアキ君は、与えられたペンキでこの設計図どおりに壁画を描くことができるか調べることにしました。
入力
N
A_1
A_2
:
A_N
H W
B_{1,1} B_{1,2} ... B_{1,W}
B_{2,1} B_{2,2} ... B_{2,W}
:
B_{H,1} B_{H,2} ... B_{H,W}
- 1行目では、使用できるペンキの数を表す整数 N (1 \leq{} N \leq{} 17) が与えられる。
- 2行目から N 行では、各ペンキの濃さを表す整数 A_i (0 \leq{} A_i \leq{} 255) が与えられる。
- N+2 行目では、設計図の高さを表す整数 H (1 \leq{} H \leq{} 200) と、設計図の幅を表す整数 W (1 \leq{} W \leq{} 200) が与えられる。
- N+3 行目から H 行は設計図の情報が与えられる。そのうちの y (1 \leq{} y \leq{} H) 行目には、各マスの番号がスペース区切りで W 個与えられる。y 行目の左側から x (1 \leq{} x \leq{} W)番目に、設計図の上から y マス、左から x マスの位置のマス目の番号、整数 B_{y,x} (0 \leq{} B_{y,x} \leq{} N - 1) が与えられる。
部分点
- 1 \leq{} N \leq{} 5 かつ 1 \leq{} H, W \leq{} 5のすべてのテストケースに正解した場合、部分点として35点を与える
- 1 \leq{} N \leq{} 9 のすべてのテストケースに正解した場合、部分点としてさらに40点を与える
出力
与えられたペンキで設計図どおりに塗ることが可能なら1、不可能なら0を1行で出力せよ。出力の末尾には改行をいれること。
入力例1
5 4 0 4 10 4 2 3 3 1 3 0 2 0
出力例1
1
与えられたペンキを上から順にA, B, C, D, Eとすると以下の順番で塗りわけることが可能です。
BBB BBB
BBB AAA
BCB AAA
BCB ADA
今回の塗り方ではEは使用しませんでした。
入力例2
5 4 0 4 10 4 2 4 3 1 2 3 0 1 2 0
出力例2
0
与えられたペンキで塗ることはできません。
入力例3
2 1 2 2 2 0 1 1 0
出力例3
0
与えられたペンキで塗ることはできません。
入力例4
5 1 1 66 30 1 5 5 3 4 4 4 2 3 4 4 0 0 3 4 4 0 0 3 3 1 0 0 3 3 1 1 2
出力例4
1
与えられたペンキを上から順にA, B, C, D, Eとすると以下の順番で塗りわけることが可能です。
A A # # # A A # # # A A # # # A A # # # A A # # #
A A B B # A A B B # A A B B # A A B B # A A B B #
A A B B E A A B B E A A B B E A A B B E A A B B E
A D D D E A D D D E A D D D E A A B B E A A B B E
A D D D E A D D C C A D D C C A A B C C A A B B E