E - Stamp Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 7 点

注意

この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

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 からはみ出していない
  • ハンコの底面は障害物が置かれているマスに重なっていない

制約

  • 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 が存在する

入力

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

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 を出力せよ。

入力例 1

3 3
...
.#.
..#
#.#
###
...

出力例 1

Yes

ハンコを回転させて、下図のように重ねると条件を満たします。緑色がハンコの底面がある部分で、灰色が障害物が置かれているマスを表します。
図

入力例 2

3 3
...
#..
#.#
.#.
.##
##.

出力例 2

No

回転と移動だけではどうやっても条件を満たすように重ねることはできません。

入力例 3

2 5
.....
..#..
..##.
.###.

出力例 3

Yes

以下のように重ねるとよいです。
図

Score : 7 points

Warning

Do not make any mention of this problem until December 27, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a grid S with H rows and W columns of squares. Let Square (i, j) denote the square at the i-th row from the top and j-th column from the left.
Some of the squares may contain obstacles.
Square (i, j) contains an obstacle if S_{i, j} is #, and it does not contain one if S_{i, j} is ..

You have a stamp whose shape is formed of squares in a grid T with H rows and W columns. More specifically, the shape of the stamp is formed of the squares (i, j) such that T_{i, j} is #.
Here, the squares that form the stamp are connected. In other words: let us call Square (i, j) valid when T_{i, j} is #. We can then travel between any two valid squares by repeatedly moving up, down, left, or right to a valid square.

You can move the stamp to any position you like and rotate it. Determine whether it is possible to position the stamp on the grid S so that the following conditions are satisfied:

  • the edges of the squares forming the stamp are all parallel to some of the edges of the squares in the grid S;
  • the stamp does not stick out of the grid S;
  • the stamp does not occupy a square containing an obstacle.

Constraints

  • 1 \le H \le 10
  • 1 \le W \le 10
  • H and W are integers.
  • S_{i, j} is # or ..
  • T_{i, j} is # or ..
  • The squares (i, j) such that T_{i, j} is # are connected.
  • S_{i, j} is . for at least one pair (i, j).
  • T_{i, j} is . for at least one pair (i, j).

Input

Input is given from Standard Input in the following format:

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}

Output

If it is possible to position the stamp so that the conditions are all satisfied, print Yes; otherwise, print No.

Sample Input 1

3 3
...
.#.
..#
#.#
###
...

Sample Output 1

Yes

We can rotate the stamp and move it to the position shown in the figure below to satisfy the conditions. In the figure, the green part represents the stamp, and the gray squares contain obstacles.

Figure

Sample Input 2

3 3
...
#..
#.#
.#.
.##
##.

Sample Output 2

No

It is impossible to position the stamp to satisfy the conditions by just moving and rotating it.

Sample Input 3

2 5
.....
..#..
..##.
.###.

Sample Output 3

Yes

We can position the stamp as follows:

Figure