레이팅 미적용스탬프 그림은 \(N \times N\) 캔버스 위의 흑백 그림으로, 어떤 칸에는 잉크가 칠해져 있고 다른 칸은 비어 있다. 이는 \(N\times N\) 문자 배열로 표현할 수 있다 (\(1\le N\le 20\)). 배열의 \(j\)번째 열의 \(i\)번째 항목은 캔버스의 해당 칸에 잉크가 있으면 *, 없으면 .이다.
베시는 만들고 싶은 스탬프 그림이 있어서, 농부 존이 이를 위해 \(K\times K\) (\(1\le K\le N\)) 스탬프 하나와 빈 \(N \times N\) 캔버스를 빌려주었다. 베시는 스탬프를 시계 방향으로 \(90^{\circ}\) 회전하는 것과, 스탬프가 격자 안에 완전히 들어가는 한 격자의 아무 곳에나 찍는 것을 반복할 수 있다. 형식적으로, 스탬프를 찍으려면 베시는 \(i \in [1,N-K+1]\)이고 \(j \in [1, N-K+1]\)인 정수 \(i,j\)를 고른다. 그러면 \(1 \le i', j' \le K\)인 각 \((i',j')\)에 대해, 스탬프의 \((i', j')\)에 잉크가 있으면 캔버스 칸 \((i+i'-1, j+j'-1)\)이 검은색으로 칠해진다. 베시는 스탬프를 찍는 사이 언제든 스탬프를 회전할 수 있다. 캔버스 칸이 한 번 검은색으로 칠해지면 계속 검은색으로 남는다.
농부 존은 베시가 자신의 스탬프로 원하는 스탬프 그림을 만들 수 있는지 궁금하다. \(T\) (\(1 \le T \le 100\))개의 테스트 케이스 각각에 대해 농부 존이 이 질문에 답하도록 도와준다.
출제자: Benjamin Qi, Claire Zhang
출제자: Benjamin Qi, Claire Zhang
입력의 첫째 줄에 테스트 케이스의 수 \(T\)가 주어진다.
각 테스트 케이스는 정수 \(N\)으로 시작하고, 이어지는 \(N\)개의 줄에 각각 와 .으로 이루어진 문자열이 주어지는데, 이는 베시가 원하는 스탬프 그림을 나타낸다. 다음 줄에 \(K\)가 주어지고, 이어지는 \(K\)개의 줄에 각각 와 .으로 이루어진 문자열이 주어지는데, 이는 농부 존의 스탬프를 나타낸다.
연속한 테스트 케이스 사이는 빈 줄로 구분된다.
각 테스트 케이스에 대해 "YES" 또는 "NO"를 한 줄에 하나씩 출력한다.
4
2
**
*.
1
*
3
.**
.**
***
2
.*
**
3
...
.*.
...
3
.*.
...
...
3
**.
.**
..*
2
.*
*.YES
YES
NO
YESIn the first test case, Bessie can perform the following sequence of stampings:
- Stamp at \((1,1)\)
- Stamp at \((1,2)\)
- Stamp at \((2,1)\)
In the second test case, Bessie can perform the following sequence of stampings:
- Stamp at \((2,2)\)
- Stamp at \((2,1)\)
- Rotate \(90^{\circ}\)
- Rotate \(90^{\circ}\)
- Stamp at \((1,2)\)
In the third test case, it is impossible to paint the middle cell.
In the fourth test case, Bessie can perform the following sequence of stampings:
- Rotate \(90^{\circ}\)
- Stamp at \((1,1)\)
- Stamp at \((1,2)\)
- Stamp at \((2,2)\)
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Bronze