페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5499

화가 곰 (Stamp Grid) 1s 32MB

문제

곰의 그림은 N \times N 도화지에 흑백 그림으로, 특정 칸은 칠해지고 특정 칸은 비어 있으며 N \times N 배열(1≤N≤20)로 표현할 수 있다.

도화지의 특정 칸에 칠해져 있으면 '*', 그렇지 않으면 '.' 으로 표현한다.

곰은 K \times K(1≤K≤N) 도장과 빈 N \times N 도화지 한 장을 가지고 있다.

곰은 도장을 시계 방향으로 90°씩 회전할 수 있으며 도장이 도화지 안에 완전히 들어있으면 그 영역에 도장을 찍을 수 있다.

정확하게는 i∈[1,N−K+1] 및 j∈[1,N−K+1]를 만족하는 정수 i,j를 선택하고 각 (i',j')에 대해 1≤i',j'≤K, 도화지에서 (i+i'−1,j+j'−1)은 도장의 (i',j')에 잉크가 있다면 검정색으로 칠해진다.

곰은 도장을 찍는 도중에 도장을 언제든 회전시킬 수 있으며 도화지에 한번 검정색으로 칠해지면 계속 검정색으로 남아있다.

곰은 자신의 도장으로 원하는 그림을 만드는 것이 가능한지 궁금하다.

각 T(1≤T≤100)개의 케이스에 대해 답을 출력하라.


입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다,

첫 줄에 N이 주어진다.

다음 N줄에 걸쳐 곰이 원하는 그림이 주어진다. 그림은 '*'과 '.'으로 이루어져 있다.

그 후 K가 주어진다.

다음 K줄에 걸쳐 곰이 가지고 있는 도장의 모양이 주어진다. 도장은 잉크가 있는 '*'과 잉크가 없는 '.'으로 이루어져 있다.

각 테스트 케이스는 빈 줄로 구분되어 주어진다.


출력

각 테스트 케이스마다 "YES" 또는 "NO"를 출력한다.


예제 

4



2

**

*.

1

*



3

.**

.**

***

2

.*

**



3

...

.*.

...

3

.*.

...

...



3

**.

.**

..*

2

.*

*.
YES

YES

NO

YES

첫 번째 테스트 케이스는 다음과 같이 도장을 찍으면 된다.

(1,1)에 도장 찍기

(1,2)에 도장 찍기

(2,1)에 도장 찍기

두 번째 테스트 케이스는 다음과 같이 도장을 찍으면 된다.

(2,2)에 도장 찍기

(2,1)에 도장 찍기

90도 도장 회전

90도 도장 회전

(1,2)에 도장 찍기

세 번째 테스트 케이스는 가운데에 색칠 할 수 없다.

네 번재 테스트 케이스는 다음과 같이 도장을 찍으면 된다.

90도 도장 회전

(1,1)에 도장 찍기

(1,2)에 도장 찍기

(2,2)에 도장 찍기


출처

USACO 2023 February Bronze
로그인해야 코드를 작성할 수 있어요.