AT_past202012_e ハンコ

[problemUrl]: https://atcoder.jp/contests/past202012-open/tasks/past202012_e $ H $ 行 $ W $ 列のマス目 $ S $ があり、上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i,\ j) $ と呼ぶことにします。 いくつかのマスには障害物が置かれているかもしれません。$ S_{i,\ j} $ が `#` ならマス $ (i,\ j) $ には障害物があり、`.` ならありません。 また、あなたはハンコを一つ持っています。このハンコの底面は $ H $ 行 $ W $ 列のマス目 $ T $ のいくつかのマスで構成される形をしています。 具体的には、このハンコの底面は $ T_{i,\ j} $ が `#` であるようなマス $ (i,\ j) $ のみを取り出してできる図形をしています。 ここで、ハンコの底面を構成するマスはひとつながりです。つまり、$ T_{i,\ j} $ が `#` であるようなマス $ (i,\ j) $ を「有効なマス」と呼ぶと、どの二つの有効なマスも、辺を共有するマスへ移動することを繰り返し、有効なマスだけを通って行き来できます。 **ハンコは移動したり、回転したりできます。**以下の条件を満たすようにマス目 $ S $ にハンコの底面を重ねることができるかを判定してください。 - ハンコの底面を構成するマスの辺は全て、マス目 $ S $ のマスのいずれかの辺と平行である - ハンコの底面はマス目 $ S $ からはみ出していない - ハンコの底面は障害物が置かれているマスに重なっていない

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_{1,\ 1}S_{1,\ 2}S_{1,\ 3}\dots\ S_{1,\ W} $ $ S_{2,\ 1}S_{2,\ 2}S_{2,\ 3}\dots\ S_{2,\ W} $ $ S_{3,\ 1}S_{3,\ 2}S_{3,\ 3}\dots\ S_{3,\ W} $ $ \hspace{40pt}\ \vdots $ $ S_{H,\ 1}S_{H,\ 2}S_{H,\ 3}\dots\ S_{H,\ W} $ $ T_{1,\ 1}T_{1,\ 2}T_{1,\ 3}\dots\ T_{1,\ W} $ $ T_{2,\ 1}T_{2,\ 2}T_{2,\ 3}\dots\ T_{2,\ W} $ $ T_{3,\ 1}T_{3,\ 2}T_{3,\ 3}\dots\ T_{3,\ W} $ $ \hspace{40pt}\ \vdots $ $ T_{H,\ 1}T_{H,\ 2}T_{H,\ 3}\dots\ T_{H,\ W} $

問題文の条件を満たすようにハンコを重ねることができるなら `Yes` を、そうでないなら `No` を出力せよ。

### 注意 この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 1\ \le\ H\ \le\ 10 $ - $ 1\ \le\ W\ \le\ 10 $ - $ S_{i,\ j} $ は `#` または `.` - $ T_{i,\ j} $ は `#` または `.` - $ T_{i,\ j} $ が `#` であるようなマス $ (i,\ j) $ はひとつながりである - 少なくとも一つ $ S_{i,\ j} $ が `.` であるような $ i,\ j $ が存在する - 少なくとも一つ $ T_{i,\ j} $ が `#` であるような $ i,\ j $ が存在する ### Sample Explanation 1 ハンコを回転させて、下図のように重ねると条件を満たします。緑色がハンコの底面がある部分で、灰色が障害物が置かれているマスを表します。 !\[図\](https://img.atcoder.jp/ghi/b2ed00b9962a7d5713a5faf85d72793a.png) ### Sample Explanation 2 回転と移動だけではどうやっても条件を満たすように重ねることはできません。 ### Sample Explanation 3 以下のように重ねるとよいです。 !\[図\](https://img.atcoder.jp/ghi/4d06863c92714324820a8581e1b1f4ad.png)