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.在进行输入的时候，注意第二个数组是横坐标逆序输入。