CCF-CSP认证 202206-2寻宝！大冒险！

题目描述

思路

有一张绿化图和藏宝图，其中绿化图很大（二维数组在限定的空间内无法存储），而藏宝图是绿化图中的一部分，对于绿化图和藏宝图，左下角的坐标为(0, 0)，右上角的坐标是(L, L)、(S, S)，其实就是坐标系。

题目保证藏宝图的左下角必定是树，因此可以从绿化图中的每一个树进行模拟，若该点(x, y)作为左下角，直到右上角(x+S, y+S)与藏宝图完全一致，说明该点符合题意，方案数量+1。

在模拟的时候要注意藏宝图不能超出绿化图的边界，然后将绿化图中的坐标映射到藏宝图的位置上，判断该位置是否为1。

代码

C++版：

#include <bits/stdc++.h>using namespace std;
int L; // 绿化图的大小，绿化图的大小比藏宝图的大太多了 
int n,S; // 西西艾弗岛上树的棵数，藏宝图的大小
int res=0; 
int main(){cin>>n>>L>>S;int green[n][2];int bao[S+1][S+1];for(int i=0;i<n;i++){cin>>green[i][0]>>green[i][1]; // 坑：输入的是坐标不是数组索引 }int num=0;for(int i=S;i>=0;i--){for(int j=0;j<S+1;j++){cin>>bao[i][j];if(bao[i][j]==1) num++; // 统计藏宝图树的数量 }}// 根据样例2可知关键应该在于边界的判断// 相当于判断小集合能否映射到大集合// 首先小集合和映射集合所含1的数量应该相等 // 小集合能通过某种关系映射到大集合for(int i=0;i<n;i++){if(green[i][0]+S>L || green[i][1]+S>L){ //超界 continue;}int tmp=0;for(int j=0;j<n;j++){ // 判断树的数目s是否对得上，减少运行时间int x=green[j][0]-green[i][0];int y=green[j][1]-green[i][1];if(x>=0&&x<=S&&y>=0&&y<=S){ // 求藏宝图范围内的树的数目 tmp++;}}if(num!=tmp){continue;}bool flag=true; // 记录结果 for(int j=0;j<n;j++){ // 映射：大集合的树的坐标差就是小集合中树的位置 int m=green[j][0]-green[i][0];int n=green[j][1]-green[i][1];if(0<=m&&m<=S&&0<=n&&n<=S){if(bao[m][n]==1){continue;}else{flag=false;break;}}}if(flag) res+=1;}	 cout<<res;return 0;
}

需要注意的地方

1.注意本题中小集合映射到大集合时不变的东西。

2.在进行输入的时候，注意第二个数组是横坐标逆序输入。