CSP 202206-2 寻宝！大冒险！ C++ 100

2023-01-07

题目

【题目背景】暑假要到了。可惜由于种种原因，小P原本的出游计划取消。失望的小P只能留在西西艾弗岛上度过一个略显单调的假期…直到… 某天，小P获得了一张神秘的藏宝图。

【问题描述】西西艾弗岛上种有棵树，这些树的具体位置记录在一张绿化图上。简单地说，西西艾弗岛绿化图可以视作一个大小为(L+1)×(L+1)的01矩阵 A, 地图左下角（坐标(0,0）)和右上角（坐标(L,L)分别对应A[O][O]和A[L][L]。其中A[i][j]=1表示坐标(i,j)处种有一棵树，A[i][j]=0则表示坐标(i,j)处没有树。换言之，矩阵A中有且仅有的 n 个 1 展示了西西艾弗岛上 n 棵树的具体位置。传说，大冒险家顿顿的宝撥就埋藏在某棵树下。并且，顿顿还从西西艾弗岛的绿化图上剪下了一小块，制作成藏宝图指示其位置。具体来说，藏宝图可以看作一个大小为(S+1)×(S+1)的01矩阵B(S远小于L),对应着A中的某一部分。理论上，绿化图A中存在着一处坐标(x,y)(0≤x,y≤L-S)与潑宝图B左下角(0,0)相对应，即满足：对B上任意一处坐标(i,j)(0≤i,j≤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≤x,y≤L且同一坐标不会重复出现。最后(S+1)行输入小P手中完整的藏宝图，其中第 i 行(0≤i≤S)包含空格分隔的(S+1)个0和1，表示B[S-i][0]···B[S-i][S]。需要注意，最先输入的是B[S][0]···B[S][S]一行，B[0][0]···B[0][S]一行最后输入。

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

【样例输入】

【样例输出】

代码

#include <bits/stdc++.h>

using namespace std;

struct node
{
  int x,y;
}tree[1005];

int main()
{
    int n,L,S;
    int B[55][55];
    int x,y,cnt=0;

    memset(B,0,sizeof(B));
    cin>>n>>L>>S;
    for(int i=0;i<n;i++)
    {
        cin>>x>>y;
        tree[i].x=x;
        tree[i].y=y;
    }
    for(int i=0;i<=S;i++)
    {
        for(int j=0;j<=S;j++)
        {
            cin>>B[S-i][j];
        }
    }
    for(int m=0;m<n;m++)
    {
        int i=0,j=0,flag=1;
        int A[55][55];
        memset(A,0,sizeof(A));
        for(int i=0;i<n;i++)
        {
            if(tree[i].x>=tree[m].x&&tree[i].x<=tree[m].x+S
               &&tree[i].y>=tree[m].y&&tree[i].y<=tree[m].y+S)
                A[tree[i].x-tree[m].x][tree[i].y-tree[m].y]=1;
        }
        for(i=0;flag&&tree[m].x+S<=L&&i<=S;i++)
        {
            for(j=0;flag&&tree[m].y+S<=L&&j<=S;j++)
            {
                if(A[i][j]!=B[i][j])
                    flag=0;
            }
        }
        if(flag==1&&i==S+1&&j==S+1)
            cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}