题解

印章 题解

问题分析

我们需要判断信纸上的墨迹图案是否可以通过多次盖章（不旋转、不超出边界、不重叠覆盖）得到。

关键约束

1. 不可旋转：印章方向固定
2. 不超出边界：每次盖章必须完全在信纸范围内
3. 不重叠覆盖：每个位置最多被覆盖一次（即最终图案中每个 x 必须来自恰好一次盖章）

算法思路

方法一：贪心匹配

基本思想：从信纸的左上角开始，找到第一个需要被覆盖的 x 位置，尝试用印章的左上角对齐该位置进行盖章。

算法步骤：

1. 预处理印章：记录印章中所有 x 的相对位置
2. 扫描信纸：从左到右、从上到下扫描信纸
3. 匹配检查：
   • 当遇到信纸上的 x 时，假设这是某个盖章的左上角对齐位置
   • 检查以该位置为左上角，是否能盖上印章（即印章的所有 x 位置在信纸上对应位置也是 x，且之前未被覆盖）
   • 如果匹配成功，标记这些位置为已覆盖
4. 验证：如果所有 x 都被成功覆盖，则输出 TAK，否则 NIE

方法二：基于第一个差异点

更高效的方法：由于印章固定，所有盖章的"模式"相同。我们可以：

1. 找到信纸上第一个 x 的位置 $(r_0, c_0)$
2. 找到印章上第一个 x 的位置 $(r_s, c_s)$
3. 确定盖章的偏移量：印章的 $(r_s, c_s)$ 应对齐信纸的 $(r_0, c_0)$
4. 检查所有可能的盖章位置是否一致

详细算法

def solve():
    q = int(input())
    for _ in range(q):
        n, m, a, b = map(int, input().split())
        letter = [input().strip() for _ in range(n)]
        stamp = [input().strip() for _ in range(a)]
        
        # 找到印章中所有墨迹点的相对坐标
        stamp_points = []
        for i in range(a):
            for j in range(b):
                if stamp[i][j] == 'x':
                    stamp_points.append((i, j))
        
        if not stamp_points:
            # 印章没有墨迹，但信纸有墨迹 -> 伪造
            print("NIE")
            continue
        
        # 创建信纸的副本用于标记覆盖
        covered = [[False] * m for _ in range(n)]
        valid = True
        
        for i in range(n):
            for j in range(m):
                if letter[i][j] == 'x' and not covered[i][j]:
                    # 尝试以(i,j)为印章左上角进行盖章
                    can_stamp = True
                    # 检查是否超出边界
                    if i + a > n or j + b > m:
                        can_stamp = False
                    else:
                        # 检查所有印章墨迹点是否匹配
                        for di, dj in stamp_points:
                            ni, nj = i + di, j + dj
                            if letter[ni][nj] != 'x' or covered[ni][nj]:
                                can_stamp = False
                                break
                    
                    if can_stamp:
                        # 标记这些位置为已覆盖
                        for di, dj in stamp_points:
                            covered[i + di][j + dj] = True
                    else:
                        valid = False
                        break
            if not valid:
                break
        
        # 检查是否所有x都被覆盖
        for i in range(n):
            for j in range(m):
                if letter[i][j] == 'x' and not covered[i][j]:
                    valid = False
                    break
            if not valid:
                break
        
        print("TAK" if valid else "NIE")

复杂度分析

• 时间复杂度：$O(q \cdot n \cdot m \cdot a \cdot b)$，最坏情况下需要检查每个位置和每个印章点
• 空间复杂度：$O(n \cdot m)$，用于存储覆盖状态
• 实际优化：由于 $n, m, a, b \leq 1000$，最坏情况 $10^{12}$ 不可行，需要优化

优化策略

1. 提前找到印章第一个点：只检查以信纸上每个 x 减去印章第一个点偏移后的位置
2. 哈希检查：使用二维哈希快速判断区域匹配
3. 一次性检查：确定一个盖章位置后，直接检查所有相关位置

样例验证

样例1

输入：
3 4 4 2
xx..
.xx.
xx..
x.
.x
x.
..

输出：TAK

分析：印章可以以不同位置多次盖章，覆盖所有信纸上的 x。

样例2

输入：
2 2 2 2
xx
xx
.x
x.

输出：NIE

分析：印章的墨迹模式与信纸不匹配，无法覆盖。

总结

本题是二维模式匹配问题，关键在于理解印章的约束条件（不旋转、不越界、不重叠）并设计高效的匹配算法。通过贪心覆盖和适当的优化，可以在合理时间内解决问题。

最终算法标签： 模式匹配 贪心算法 二维覆盖 模拟