邮票画是一幅在N×N画布上的黑白画，其中某些单元格是着墨的，而其他单元格是空白的。它可以用N×N个字符数组（1≤N≤20）来描述。如果画布在该正方形和处包含墨水，则数组第j列的第i项等于*。否则
贝西有一张她想创作的邮票画，所以农夫约翰借给她一张K×K（1≤K≤N）邮票和一张空的N×N画布。Bessie可以将印章顺时针旋转90∘，并在网格上的任何位置盖章，只要印章完全在网格内。形式上，为了盖章，Bessie选择整数i，j，使得i∈[1，N−K+1]和j∈[1、N−K+1]；对于每个（i′，j′），使得1≤i′，j′≤K，画布单元（i+i′−1，j+j′−1）被涂成黑色，如果邮票在（i′、j′）处有墨水。贝西可以在冲压之间随时旋转印章。画布单元格一旦涂成黑色，它将保持黑色。
农夫约翰想知道贝西是否有可能用他的邮票创作出她想要的邮票。对于每个T（1≤T≤100）测试用例，帮助Farmer John回答这个问题。
INPUT FORMAT（输入来自终端/stdin）：
输入的第一行包含T，即测试用例的数量。
每个测试用例都以一个整数N开头，后跟N行，每行包含一个s和.s字符串，表示Bessie所需的邮票绘画。下一行包含K，后面是K行，每行包含一个和.s字符串，代表Farmer John的邮票。
连续的测试用例用换行符分隔。
OUTPUT FORMAT（输出格式）（将输出打印到终端/标准输出）：
对于每个测试用例，在单独的行上输出“YES”或“NO”。
样本输入：
4.
2.
**
*.
1.
*
3.
.**
.**
2.
.*
**
3.
...
.*.
...
3.
.*.
...
...
3.
**.
.**
..*
2.
.*
*.
样本输出：
YES
YES
NO
YES
在第一个测试用例中，Bessie可以执行以下冲压顺序：
在（1,1）处盖章
在（1,2）处盖章
盖章（2,1）
在第二个测试用例中，Bessie可以执行以下冲压顺序：
盖章（2,2）
盖章（2,1）
旋转90∘
旋转90∘
在（1,2）处盖章
在第三个测试用例中，不可能绘制中间单元格。
在第四个测试用例中，Bessie可以执行以下冲压顺序：
旋转90∘
在（1,1）处盖章
在（1,2）处盖章
盖章（2,2）
这是今天学校布置的题目，我不会，希望各位帮忙解答一下（用C++的算法进行），最希望给出代码和思路！
该回答引用GPTᴼᴾᴱᴺᴬᴵ
这个问题可以用字符串匹配的方法解决。具体地，对于每个可能的盖章位置，在画布上匹配邮票图案。如果匹配成功，则返回“YES”，否则继续搜索下一个位置。如果所有可能的位置都搜索完了，返回“NO”。
具体地说，对于每个可能的盖章位置，可以用双重循环遍历邮票和画布上的所有单元格，检查是否匹配。匹配的标准是：如果邮票图案在（i', j'）处有墨水，则在画布上的（i+i'-1, j+j'-1）处也必须有墨水。如果匹配失败，则继续搜索下一个位置。如果所有的位置都尝试了，但没有找到一个匹配，那么返回“NO”。
需要注意的是，在检查匹配时，可能会越界。因此，需要在循环中进行一些边界检查。
下面是一个Python实现的例子：
def rotate_stamp(stamp):
"""将邮票顺时针旋转90度"""
rotated_stamp = []
for i in range(len(stamp[0])):
row = ""
for j in range(len(stamp)-1, -1, -1):
row += stamp[j][i]
rotated_stamp.append(row)
return rotated_stamp
def check_stamp(stamp, canvas, i, j):
"""检查邮票是否可以盖到画布的位置i,j"""
for x in range(len(stamp)):
for y in range(len(stamp)):
if stamp[x][y] == "*" and canvas[i+x][j+y] == ".":
canvas[i+x] = canvas[i+x][:j+y] + "*" + canvas[i+x][j+y+1:]
elif stamp[x][y] == "*" and canvas[i+x][j+y] == "*":
return False
return True
def solve(stamp, canvas, n, k):
"""尝试在画布上盖邮票"""
for i in range(n-k+1):
for j in range(n-k+1):
for _ in range(4):
if check_stamp(stamp, canvas, i, j):
return True
stamp = rotate_stamp(stamp)
return False
t = int(input())
for _ in range(t):
n = int(input())
canvas = []
for _ in range(n):
row = input().strip()
canvas.append(row)
k = int(input())
stamp = []
for _ in range(k):
row = input().strip()
stamp.append(row)
for _ in range(3):
stamp = rotate_stamp(stamp)
if solve(stamp, canvas, n, k):
print("YES")
break
else:
print("NO")
这个代码中，rotate_stamp函数用于将邮票顺时针旋转90度。check_stamp函数用于检查邮票是否可以盖到画布的某个位置。solve函数用于尝试在画布上盖邮票，如果成功就返回True，否则返回False。在主程序中，我们读入输入，尝试将邮票盖到画布上，如果成功则输出"YES"，否则输出"NO"。在尝试将邮票旋转3次后仍然无法将邮票盖到画布上，则输出"NO"。