秀洲住房与建设局网站,网站后台模板 如何使用,专业建设费用怎么花,公司网站asp源码CCF-CSP 202206-2 寻宝#xff01;大冒险#xff01; #x1f638;题目要求#x1f408;⬛题目背景#x1f408;⬛问题描述#x1f408;⬛输入格式#x1f408;⬛输出格式#x1f408;⬛样例说明#x1f3b6;样例1输入#x1f3b6;样例1输出#x1f3b6;样… CCF-CSP 202206-2 寻宝大冒险 题目要求⬛题目背景⬛问题描述⬛输入格式⬛输出格式⬛样例说明样例1输入样例1输出样例1解释样例2输入样例2输出样例2解释 ⬛子任务⬛提示 问题解决满分代码含逐行代码解释C 场景拓展 题目要求
⬛题目背景
暑假要到了。可惜由于种种原因小 P 原本的出游计划取消。失望的小 P 只能留在西西艾弗岛上度过一个略显单调的假期……直到……
某天小 P 获得了一张神秘的藏宝图。
⬛问题描述
西西艾弗岛上种有 n n n 棵树这些树的具体位置记录在一张绿化图上。
简单地说西西艾弗岛绿化图可以视作一个大小为 ( L 1 ) × ( L 1 ) (L1)×(L1) (L1)×(L1) 的 01 01 01 矩阵 A A A地图左下角坐标 ( 0 , 0 ) (0,0) (0,0)和右上角坐标 ( L , L ) (L,L) (L,L)分别对应 A [ 0 ] [ 0 ] A[0][0] A[0][0] 和 A [ L ] [ L ] A[L][L] A[L][L]。其中 A [ i ] [ j ] 1 A[i][j]1 A[i][j]1 表示坐标 ( i , j ) (i,j) (i,j) 处种有一棵树 A [ i ] [ j ] 0 A[i][j]0 A[i][j]0 则表示坐标 ( i , j ) (i,j) (i,j) 处没有树。换言之矩阵 A A A 中有且仅有的 n n n 个 1 1 1 展示了西西艾弗岛上 n n n 棵树的具体位置。
传说大冒险家顿顿的宝藏就埋藏在某棵树下。并且顿顿还从西西艾弗岛的绿化图上剪下了一小块制作成藏宝图指示其位置。
具体来说藏宝图可以看作一个大小为 ( S 1 ) × ( S 1 ) (S1)×(S1) (S1)×(S1) 的 01 01 01 矩阵 B B B S S S 远小于 L L L对应着 A A A 中的某一部分。理论上绿化图 A A A 中存在着一处坐标 ( x , y ) (x,y) (x,y) 0 ≤ x , y ≤ L − S 0 \leq x,y \leq L-S 0≤x,y≤L−S与藏宝图 B B B 左下角 ( 0 , 0 ) (0,0) (0,0) 相对应即满足对 B B B 上任意一处坐标 ( i , j ) (i,j) (i,j) 0 ≤ i , j ≤ S 0 \leq i,j \leq S 0≤i,j≤S都有 A [ x i ] [ y i ] B [ i ] [ j ] A[xi][yi]B[i][j] A[xi][yi]B[i][j]。当上述条件满足时我们就认为藏宝图 B B B 对应着绿化图 A A A 中左下角为 ( x , y ) (x,y) (x,y)、右上角为 ( x S , y S ) (xS,yS) (xS,yS) 的区域。
实际上考虑到藏宝图仅描绘了很小的一个范围满足上述条件的坐标 ( x , y ) (x,y) (x,y) 很可能存在多个。请结合西西艾弗岛绿化图中 n n n 棵树的位置以及小 P 手中的藏宝图判断绿化图中有多少处坐标满足条件。
特别地藏宝图左下角位置一定是一棵树即 A [ x ] [ y ] B [ 0 ] [ 0 ] 1 A[x][y]B[0][0]1 A[x][y]B[0][0]1表示了宝藏埋藏的位置。
⬛输入格式
从标准输入读入数据。
输入的第一行包含空格分隔的三个正整数 n n n、 L L L 和 S S S分别表示西西艾弗岛上树的棵数、绿化图和藏宝图的大小。
由于绿化图尺寸过大输入数据中仅包含 n n n 棵树的坐标而非完整的地图即接下来 n n n 行每行包含空格分隔的两个整数 x x x 和 y y y表示一棵树的坐标满足 0 ≤ x , y ≤ L 0 \leq x,y \leq L 0≤x,y≤L 且同一坐标不会重复出现。
最后 ( S 1 ) (S1) (S1) 行输入小 P 手中完整的藏宝图其中第 i i i 行 0 ≤ i ≤ S 0 \leq i \leq S 0≤i≤S包含空格分隔的 ( S 1 ) (S1) (S1) 个 0 0 0 和 1 1 1表示 B [ S − i ] [ 0 ] ⋅ ⋅ ⋅ B [ S − i ] [ S ] B[S-i][0]···B[S-i][S] B[S−i][0]⋅⋅⋅B[S−i][S]。
需要注意最先输入的是 B [ S ] [ 0 ] ⋅ ⋅ ⋅ B [ S ] [ S ] B[S][0]···B[S][S] B[S][0]⋅⋅⋅B[S][S] 一行 B [ 0 ] [ 0 ] ⋅ ⋅ ⋅ B [ 0 ] [ S ] B[0][0]···B[0][S] B[0][0]⋅⋅⋅B[0][S] 一行最后输入。
⬛输出格式
输出到标准输出。
输出一个整数表示绿化图中有多少处坐标可以与藏宝图左下角对应即可能埋藏着顿顿的宝藏。
⬛样例说明
样例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 ) (0,0) (0,0)、 ( 1 , 1 ) (1,1) (1,1) 和 ( 2 , 2 ) (2,2) (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 ) (3,3) (3,3) 处对应则藏宝图右上角会超出绿化图边界对应不成功。
⬛子任务
40% 的测试数据满足 L ≤ 50 L \leq 50 L≤50
70% 的测试数据满足 L ≤ 2000 L \leq 2000 L≤2000
全部的测试数据满足 n ≤ 1000 n \leq 1000 n≤1000、 L ≤ 1 0 9 L \leq 10^9 L≤109 且 S ≤ 50 S \leq 50 S≤50。
⬛提示
实际测试数据中不包括答案为 0 0 0 的用例。
问题解决
满分代码含逐行代码解释
C
#includebits/stdc.h
using namespace std;mappairint, int, inttree; //pair表示的是坐标(x,y)映射到0或1上即有没有树
int n, L, S;
int A[1010][2];
int B[51][51];bool check(int x, int y){if(x S L || y S L) return false; //排除藏宝图过大的情况 for(int i 0; i S; i){for(int j 0; j S; j){if(B[i][j] 1){if(tree.count({xi, yj}) ! 1) return false;}if(B[i][j] 0){if(tree.count({xi, yj}) 1) return false;}}} return true;
}int main(){cin n L S;for(int i 0; i n; i){cin A[i][0] A[i][1];tree[{A[i][0], A[i][1]}] 1;} for(int i S; i 0; i--){for(int j 0; j S; j){cin B[i][j]; //注意题目中所描述的矩阵B的形状 }}int result 0;for(int i 0; i n; i){if(check(A[i][0], A[i][1])) result;}cout result endl;return 0;
}场景拓展
本题代码主要涉及到二维空间内的模式识别和匹配问题本题代码的核心思想是在一个大的数据集中寻找与给定模式完全匹配的子集它通过对给定区域内的特定模式在这个例子中是树木的分布进行搜索和验证。
地图或矩阵匹配问题在一个大的二维数组如地图、森林中寻找与给定小矩阵如藏宝图、特定图案完全匹配的区域。这类问题常见于图像处理、游戏开发如寻宝、迷宫探索和模式识别领域。环境模拟与分析在生态学、城市规划或农业科学等领域模拟特定环境下的分布情况如树木、建筑物或其他自然或人造物的分布并分析其对环境的影响或符合特定条件的区域。图像处理与识别虽然本题代码示例是以文本形式处理数据但相似的逻辑可以应用于图像识别中比如寻找图像中的特定标志、图案或对象。这需要将图像数据转换为二维数组或矩阵并定义匹配规则。游戏开发中的关卡设计与检测在某些类型的游戏中可能需要检测地图上是否存在符合特定规则的结构或模式如检查玩家是否按照特定的布局建造了建筑物或其他物体。
