【寒假每日一题】AcWing 4510. 寻宝！大冒险！
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
目录
一、题目
1、原题链接
2、题目描述
暑假要到了。
可惜由于种种原因小 P原本的出游计划取消。
失望的小 P 只能留在西西艾弗岛上度过一个略显单调的假期……直到……
某天小 P 获得了一张神秘的藏宝图。
西西艾弗岛上种有 n 棵树这些树的具体位置记录在一张绿化图上。
简单地说西西艾弗岛绿化图可以视作一个大小为 (L+1)×(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)×(S+1) 的 01 矩阵 BS 远小于 L对应着 A 中的某一部分。
理论上绿化图 A 中存在着一处坐标 (x,y)0≤x,y≤L−S与藏宝图 BB 左下角 (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]一行最后输入。
输出格式
输出一个整数表示绿化图中有多少处坐标可以与藏宝图左下角对应即可能埋藏着顿顿的宝藏。
数据范围
40% 的测试数据满足L≤50
70% 的测试数据满足L≤2000
全部的测试数据满足n≤1000、L≤10^9 且 S≤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
3样例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输出样例2
0样例2解释
如果将藏宝图左下角与绿化图 (3,3) 处对应则藏宝图右上角会超出绿化图边界对应不成功。
二、解题报告
思路来源y总相亲的时候月薪8000体制内和月薪2万程序员该选哪个呢每日一题_哔哩哔哩_bilibili
y总yyds
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 <iostream>
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中对应范围中的树也就说明
了满足上述条件这个树点就满足题目要求。
*/