C++算法题（不超过普及难度）

Question

邮票画是一幅在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++的算法进行），最希望给出代码和思路！

Answer 1

该回答引用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"。