题目描述

题目描述了一个寻宝问题。给你一个很大的地图（绿化图 A），上面有一些树。你还有一个小的藏宝图（B），它对应着大地图的某一部分。你的目标是找到大地图上有多少个位置，使得把藏宝图放在这个位置上，藏宝图上的树的分布和大地图上对应位置的树的分布完全一致，题目描述比较繁琐，总结为以下几点：

1. 绿化图 A: 一个很大的 01 矩阵，1 表示树，0 表示空地。尺寸为 (L+1) x (L+1)。 由于 L 很大，A 不会直接给出，而是给出 n 棵树的坐标。
2. 藏宝图 B: 一个小的 01 矩阵，尺寸为 (S+1) x (S+1)。 S 远小于 L。藏宝图的内容是直接给出的。
3. 匹配: 你需要找到 A 中所有可能的左下角坐标 (x, y)，使得以 (x, y) 为左下角、尺寸为 (S+1) x (S+1) 的区域与藏宝图 B 完全匹配。
4. 树的限制: 藏宝图的左下角 (0, 0) 必须是一棵树 (B[0][0] = 1)，并且匹配的区域在大地图上也必须是一棵树 (A[x][y] = 1)。 这意味着宝藏埋在树下。
5. 坐标范围: 0 ≤ x, y ≤ L - S，确保藏宝图不会超出绿化图。

Python 代码

import sys


read_line = sys.stdin.readline

n, l, s = map(int, read_line().split())
trees = set()
for _ in range(n):
    x, y = map(int, read_line().split())
    trees.add((x, y))

treasure_map = []
for _ in range(s + 1):
    treasure_map.append(list(map(int, read_line().split())))

treasure_map.reverse()

count = 0
for x, y in trees:
    if x + s > l or y + s > l:
        continue

    match = True
    for i in range(s + 1):
        for j in range(s + 1):
            if treasure_map[i][j] == 1 and (x+i, y+j) not in trees:
                match = False
                break
            elif treasure_map[i][j] == 0 and (x+i, y+j) in trees:
                match = False
                break
        if not match:
            break

    if match:
        count += 1

print(count)