目录
一、题目
二、解题报告
一、题目
1、原题链接
2、题目描述
5 100 2
0 0
1 1
2 2
3 3
4 4
0 0 1
0 1 0
1 0 0
3
5 4 2
0 0
1 1
2 2
3 3
4 4
0 0 0
0 1 0
1 0 0
0
二、解题报告
1、思路分析
1)枚举每棵树的位置，针对每棵树的位置，使其按题目要求，作为B[0][0]，依据题意来判断是否满足要求，统计出满足的个数，输出，即为所求。
2)判断是否满足时，可以依次枚举每棵树，作为B[0][0]，然后将B中的每个点与A中对应范围内的每个点依次进行判断是否值相等（可以先将对应范围的区域“剪裁”下来作为一个数组（开一个和B一样大的数组，来存储A中对应范围的情况–是否有树），然后用B来与其进行逐个点的比较），即可；也可以先统计出B中树的数目，然后再在A中对应的B范围内的树来依次判断B中对应的点是否也是树，如果满足此条件，而且A中对应的B范围内的树的数量和输入的B中树的数量相等，可以判定这个树的坐标作为B[0][0]满足题目要求。
2、时间复杂度
时间复杂度为O(n^2)
3、代码详解
#include
using namespace std;
typedef long long LL;
#define x first
#define y second
pair<int,int> p[1010];
int B[55][55];
int main()
{ int n,S;
LL L;
cin>>n>>L>>S;
for(int i=0;i<n;i++){
cin>>p[i].x>>p[i].y;
}
int treeB=0; //记录B中树的数量
for(int i=S;i>=0;i–){
for(int j=0;j<=S;j++){
cin>>B[i][j];
if(B[i][j])
treeB++;
}
}
int ans=0; //记录结果
for(int i=0;i<n;i++){
//记录当前遍历的树的坐标
int nx=p[i].x,ny=p[i].y;
//BSx,BSy代表藏宝图对应在绿化图上的B[S][S]的横纵坐标
int BSx=p[i].x+S,BSy=p[i].y+S;
//如果B[S][S]超出了绿化图的范围不操作
if(BSx>L||BSy>L) continue;
int numt=0; //记录绿化图中对应藏宝图范围内的树的总数
bool flag=true; //记录是否A中对应范围内的树，在B中都有对应
for(int j=0;j<n;j++){
//如果树的坐标恰好在藏宝图的范围中
if(p[j].x>=nx&&p[j].x<=BSx&&p[j].y>=ny&&p[j].y<=BSy){
//判断这棵树在输入的B中是否存在
if(B[p[j].x-nx][p[j].y-ny])
numt++;
else flag=false;
}
}
if(numt==treeB&&flag) ans++;
}
cout<<ans;
return 0;
}
/*注： 两个范围内树的数量相等，不一定能够匹配
因为树的分布可能不同，所以只有保证在A中对应藏宝图范围内的每棵树，在输入的B中对应位置也是树
这就保证了B中一定包含了绿化图对应范围内的树，但是也可能在此之上还有别的树，因为我们是用A中
对应范围内的每棵树来与B范围内相应的树进行判断，说明B中树在满足此条件后，还有其他树，所以在
此条件下保证两个范围内的树的总数一致，就能保证B中的树一定全都是A中对应范围中的树，也就说明
了满足上述条件，这个树点就满足题目要求。
*/
