寻宝！大冒险！（2023寒假每日一题 17）

暑假要到了。

可惜由于种种原因，小 $P$ 原本的出游计划取消。

失望的小 $P$ 只能留在西西艾弗岛上度过一个略显单调的假期……直到……

某天，小 $P$ 获得了一张神秘的藏宝图。

西西艾弗岛上种有 $n$ 棵树，这些树的具体位置记录在一张绿化图上。

简单地说，西西艾弗岛绿化图可以视作一个大小为 $(L+1)\times (L+1)$ 的 $01$ 矩阵 $A$ ，地图左下角（坐标 $(0,0)$ ）和右上角（坐标 $(L,L)$ ）分别对应 $A[0][0]$ 和 $A[L][L]$ 。

其中 $A[i][j]=1$ 表示坐标 $(i,j)$ 处种有一棵树，$A[i][j]=0$ 则表示坐标 $(i,j)$ 处没有树。

换言之，矩阵 $A$ 中有且仅有的 $n$ 个 $1$ 展示了西西艾弗岛上 $n$ 棵树的具体位置。

传说，大冒险家顿顿的宝藏就埋藏在某棵树下。

并且，顿顿还从西西艾弗岛的绿化图上剪下了一小块，制作成藏宝图指示其位置。

具体来说，藏宝图可以看作一个大小为 $(S+1)\times (S+1)$ 的 $01$ 矩阵 $B$ （$S$ 远小于 $L$），对应着 $A$ 中的某一部分。

理论上，绿化图 $A$ 中存在着一处坐标 $(x,y)（0\le x,y\le L-S）$与藏宝图 $B$ 左下角 $(0,0)$ 相对应，即满足：

对 $B$ 上任意一处坐标 $(i,j)（0\le i,j\le S）$，都有 $A[x+i][y+j]=B[i][j]$ 。

当上述条件满足时，我们就认为藏宝图 $B$ 对应着绿化图 A 中左下角为 $(x,y)$ 、右上角为 $(x+S,y+S)$ 的区域。

实际上，考虑到藏宝图仅描绘了很小的一个范围，满足上述条件的坐标 $(x,y)$ 很可能存在多个。

请结合西西艾弗岛绿化图中 $n$ 棵树的位置，以及小 $P$ 手中的藏宝图，判断绿化图中有多少处坐标满足条件。

特别地，藏宝图左下角位置一定是一棵树，即 $A[x][y]=B[0][0]=1$ ，表示了宝藏埋藏的位置。

输入格式
输入的第一行包含空格分隔的三个正整数 $n、L$ 和 $S$ ，分别表示西西艾弗岛上树的棵数、绿化图和藏宝图的大小。

由于绿化图尺寸过大，输入数据中仅包含 n 棵树的坐标而非完整的地图；即接下来 n 行每行包含空格分隔的两个整数 $x$ 和 $y$ ，表示一棵树的坐标，满足 $0\le x,y\le L$ 且同一坐标不会重复出现。

最后 $(S+1)$ 行输入小 $P$ 手中完整的藏宝图，其中第 $i$ 行$（0\le i\le S）$包含空格分隔的 $(S+1)$ 个 $0$ 和 $1$ ，表示 $B[S-i][0]\cdots B[S-i][S]$ 。 需要注意，最先输入的是 $B[S][0]\cdots B[S][S]$ 一行，$B[0][0]\cdots B[0][S]$ 一行最后输入。

输出格式
输出一个整数，表示绿化图中有多少处坐标可以与藏宝图左下角对应，即可能埋藏着顿顿的宝藏。

数据范围
$40\%$ 的测试数据满足：$L\le 50$； $70\%$ 的测试数据满足：$L\le 2000$ ； 全部的测试数据满足：$n\le 1000、L\le 10^9$ 且 $S\le 50$ 。

输入样例1：

5 100 2
0 0
1 1
2 2
3 3
4 4
0 0 1
0 1 0
1 0 0
1
2
3
4
5
6
7
8
9

输出样例1：

3
1

样例1解释
绿化图上 $(0,0)、(1,1)和(2,2)$ 三处均可能埋有宝藏。

输入样例2：

5 4 2
0 0
1 1
2 2
3 3
4 4
0 0 0
0 1 0
1 0 0
1
2
3
4
5
6
7
8
9

输出样例2：

0
1

样例2解释
如果将藏宝图左下角与绿化图 (3,3) 处对应，则藏宝图右上角会超出绿化图边界，对应不成功。

---

#include
#include

#define x first
#define y second

using namespace std;

const int N = 1010, M = 55, d = 1e9;

typedef long long LL;
typedef pair<int, int> PII;

int n, L, S;
bool b[M][M];
PII q[N];
unordered_map<LL, bool> st; 

int main(){
    
    cin >> n >> L >> S;
    for(int i = 0; i < n; i++){
        cin >> q[i].x >> q[i].y;
        st[q[i].x*d + q[i].y] = 1;
    } 
    for(int i = 0; i <= S; i++)
        for(int j = 0; j <= S; j++)
            cin >> b[S-i][j];
    // 遍历n个点
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(q[i].x + S > L || q[i].y + S > L) continue;
        // 遍历藏宝图
        bool flag = true;
        for(int l = 0; l <= S; l++)
            for(int m = 0; m <= S; m++){
                if(b[l][m] && !st.count((q[i].x + l)*d+(q[i].y + m))){
                    flag = false;
                    break;
                }else if(!b[l][m] && st.count((q[i].x + l)*d+(q[i].y + m))){
                    flag = false;
                    break;
                }
            }
            
        if(flag) ans++;
    }
    cout << ans << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50