파일 업로드

🎨AI 리소스 생성

프롬프트 없음

흑색 도장 그림

  • 시뮬레이션
  • 완전 탐색
profile
실행 시간 제한메모리 제한
2 초1024 MB
📃 해결할 문제

선호와 선영은 함께 예술 작업을 시작하기로 결정했습니다. 그들이 선택한 프로젝트는 N×NN \times N 캔버스 위의 흑백 도장 그림으로, 특정 칸은 두꺼운 잉크가 묻어있고, 다른 칸은 비어 있습니다. 이 그림은 N×NN \times N 문자의 배열(1≤N≤201 \le N \le 20)로 표현될 수 있습니다. 배열의 jj번째 열의 ii번째 항목은 해당 칸에 잉크가 있으면 '*'이고, 그렇지 않으면 '.'로 표시됩니다.

 

선영은 자신만의 도장 그림을 만들고 싶어합니다. 그래서 선호는 그녀에게 K×KK \times K (1≤K≤N1 \le K \le N) 크기의 하나의 도장과 빈 N×NN \times N 캔버스를 빌려 주었습니다. 선영은 도장을 90∘90^{ \circ} 회전시키며 원하는 곳 어디든 도장을 찍을 수 있습니다.

단, 도장은 캔버스 안에 완전히 들어가있어야 합니다. 선영은 i∈[1,N−K+1]i \in [1, N-K+1] 그리고 j∈[1,N−K+1]j \in [1, N-K+1]인 정수를 선택할 수 있고, 1≤i′,j′≤K1 \le i', j' \le K를 만족하는 모든 (i′,j′)(i',j')에 대해, 도장의 (i′,j′)(i', j')에 잉크가 있다면 캔버스의 (i+i′−1,j+j′−1)(i+i'-1, j+j'-1)칸을 검은색으로 칠합니다. 선영은 언제든지 도장을 찍는 사이에 도장을 회전시킬 수 있습니다. 한 번 캔버스 칸이 검정색으로 칠해지면, 계속 검정색을 유지합니다.

 

선호는 선영이 그의 도장으로 원하는 도장 그림을 만들 수 있는지 궁금합니다. TT (1≤T≤1001 \le T \le 100)개의 테스트 케이스에 대해, 선호가 질문에 답할 수 있도록 도와주세요.

💻 입력

입력의 첫 번째 줄에는 테스트 케이스의 수 TT가 포함됩니다.

각 테스트 케이스는 선영의 도장 그림을 나타내는 '*'와'.'의 문자열을 포함하는 NN가 다음에 오고, 그 다음 줄에는 NN 줄이 옵니다. 다음 줄에는 KK가 있고, 그에 이어 KK 줄이 각 선호의 도장을 나타내는 '*'와 '.'의 문자열을 포함합니다.

연속된 테스트 케이스는 줄바꿈으로 구분됩니다.

🖨️ 출력
각 테스트 케이스마다, 'YES' 또는 'NO'를 별도의 줄에 출력하세요.
💻 예제 입력 1
4

2
**
*.
1
*

3
.**
.**
***
2
.*
**

3
...
.*.
...
3
.*.
...
...

3
**.
.**
..*
2
.*
*.
🖨️ 예제 출력 1
YES
YES
NO
YES
💡 힌트

첫 번째 테스트 케이스에서 선영은 다음과 같은 도장 찍기 순서를 수행할 수 있습니다:

  1. (1,1)(1,1)에 도장 찍기
  2. (1,2)(1,2)에 도장 찍기
  3. (2,1)(2,1)에 도장 찍기

두 번째 테스트 케이스에서 선영은 다음과 같은 도장 찍기 순서를 수행할 수 있습니다:

  1. (2,2)(2,2)에 도장 찍기
  2. (2,1)(2,1)에 도장 찍기
  3. 90∘90^{ \circ} 회전
  4. 90∘90^{ \circ} 회전
  5. (1,2)(1,2)에 도장 찍기

세 번째 테스트 케이스에서 가운데 칸을 칠하는 것은 불가능합니다.

네 번째 테스트 케이스에서 선영은 다음과 같은 도장 찍기 순서를 수행할 수 있습니다:

  1. 90∘90^{ \circ} 회전
  2. (1,1)(1,1)에 도장 찍기
  3. (1,2)(1,2)에 도장 찍기
  4. (2,2)(2,2)에 도장 찍기

출처: USACO 2023 February Contest, Bronze Problem 2. Stamp Grid