Lưới Đóng Dấu

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie muốn tạo một bức tranh trên lưới $N \times N$ bằng một con dấu $K \times K$ . Cô ấy có thể xoay con dấu theo chiều kim đồng hồ $90 °$ bất kỳ số lần, và đóng dấu tại bất kỳ vị trí nào sao cho con dấu nằm hoàn toàn trong lưới. Khi một ô đã được tô đen thì nó giữ nguyên màu đen.

Cho bức tranh mong muốn và hình dạng con dấu, hãy xác định liệu bức tranh có thể được tạo ra hay không.

Dữ liệu vào

Dòng 1: Số nguyên $T$ ( $1 \leq T \leq 100$ ) — số bộ test.
Mỗi bộ test:
- Một số nguyên $N$ ( $1 \leq N \leq 20$ )
- $N$ dòng, mỗi dòng $N$ ký tự * (đen) hoặc . (trắng) — lưới mong muốn
- Một số nguyên $K$ ( $1 \leq K \leq N$ )
- $K$ dòng, mỗi dòng $K$ ký tự * hoặc . — hình dạng con dấu

Dữ liệu ra

Với mỗi bộ test, in YES nếu có thể tạo được bức tranh, ngược lại in NO.

Ràng buộc

$1 \leq T \leq 100$
$1 \leq N \leq 20$
$1 \leq K \leq N$

Ví dụ

Input	Output	Giải thích
4 2 ** . 1 3 . . *** 2 .* ** 3 ... .. ... 3 .. ... ... 3 . . ..* 2 .* *.	YES YES NO YES	Test 1: Dùng dấu 1x1 tô từng ô. Test 3: Ô giữa không thể tô được bằng dấu 3x3 có dấu ở góc trên.

Bình luận

Không có bình luận tại thời điểm này.