做数学题好的网站,做网站的又营业执照的吗,做网站开发 用的最多的语言,专业培训大全题目背景
暑假要到了。可惜由于种种原因#xff0c;小 P 原本的出游计划取消。失望的小 P 只能留在西西艾弗岛上度过一个略显单调的假期……直到……
某天#xff0c;小 P 获得了一张神秘的藏宝图。
问题描述
西西艾弗岛上种有 n 棵树#xff0c;这些树的具体位置记录在…题目背景
暑假要到了。可惜由于种种原因小 P 原本的出游计划取消。失望的小 P 只能留在西西艾弗岛上度过一个略显单调的假期……直到……
某天小 P 获得了一张神秘的藏宝图。
问题描述
西西艾弗岛上种有 n 棵树这些树的具体位置记录在一张绿化图上。 简单地说西西艾弗岛绿化图可以视作一个大小为 (L1)×(L1) 的 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 棵树的具体位置。
传说大冒险家顿顿的宝藏就埋藏在某棵树下。 并且顿顿还从西西艾弗岛的绿化图上剪下了一小块制作成藏宝图指示其位置。 具体来说藏宝图可以看作一个大小为 (S1)×(S1) 的 01 矩阵 BS 远小于 L对应着 A 中的某一部分。 理论上绿化图 A 中存在着一处坐标 (x,y)0≤x,y≤L−S与藏宝图 B 左下角 (0,0) 相对应即满足 对 B 上任意一处坐标 (i,j)0≤i,j≤S都有 A[xi][yj]B[i][j]。 当上述条件满足时我们就认为藏宝图 B 对应着绿化图 A 中左下角为 (x,y)、右上角为 (xi,yj) 的区域。
实际上考虑到藏宝图仅描绘了很小的一个范围满足上述条件的坐标 (x,y) 很可能存在多个。 请结合西西艾弗岛绿化图中 n 棵树的位置以及小 P 手中的藏宝图判断绿化图中有多少处坐标满足条件。
特别地藏宝图左下角位置一定是一棵树即 A[x][y]B[0][0]1表示了宝藏埋藏的位置。
输入格式
从标准输入读入数据。
输入的第一行包含空格分隔的三个正整数 n、L 和 S分别表示西西艾弗岛上树的棵数、绿化图和藏宝图的大小。
由于绿化图尺寸过大输入数据中仅包含 n 棵树的坐标而非完整的地图即接下来 n 行每行包含空格分隔的两个整数 x 和 y表示一棵树的坐标满足 0≤x,y≤L 且同一坐标不会重复出现。
最后 (S1) 行输入小 P 手中完整的藏宝图其中第 i 行0≤i≤S包含空格分隔的 (S1) 个 0 和 1表示 B[S−i][0]⋯B[S−i][S]。需要注意最先输入的是 B[S][0]⋯B[S][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)、(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) 处对应则藏宝图右上角会超出绿化图边界对应不成功。
子任务
40% 的测试数据满足L≤50
70% 的测试数据满足L≤2000
全部的测试数据满足n≤1000、L≤ 且 S≤50。
提示
实际测试数据中不包括答案为 0 的用例。
思路 1、查看测试数据可知遍历绿化图肯定会超时因为最大可达10的9次方观察题目发现藏宝图左下角位置一定是一棵树即 A[x][y]B[0][0]1表示了宝藏埋藏的位置而绿化图中树的个数最多只有1000棵可在满足藏宝图左下角的而情况下遍历绿化图中的每一棵树来进行判断。 2、若藏宝图中有一个位置的01情况与绿化图中不一致则直接遍历下一棵树。 代码实现
#includeiostream
#includevector
#includemap
#includealgorithm
using namespace std;int main() {int n, L, S;cin n L S;mappairint,int, intTree;vectorvectorintGraph;for (int i 0; i n; i) { //利用一个有序哈希表来存储绿化图中哪些点有坐标int x, y; cin x y;Tree[{x,y}]; //其中哈希表的key为两个坐标value使其等于1表示该点有树}for (int i 0; i S; i) { //藏宝图坐标的输入vectorinttmp;for (int j 0; j S; j) {int x;cin x;tmp.push_back(x);}Graph.push_back(tmp); }reverse(Graph.begin(), Graph.end()); //题目说明藏宝图的最后一次输入是第一行所以进行一次反转int res 0;//测试数据L最大可达10的9次方遍历绿化图显然不切合实际题目说明藏宝图左下角位置一定是一棵树//即Graph[0][0]1表示了宝藏埋藏的位置,因此以绿化图的每一棵树作为藏宝图左下角为起点遍历藏宝图来进行判断因为藏宝图的大小S最大也为50for (auto s : Tree) { //表示以绿化图的每一棵树坐标开始 if (s.first.first S L || s.first.second S L) //绿化图起始坐标加上藏宝图大小越界绿化图则直接continuecontinue;else {int i, j;bool flag true; //此标志位是为了跳出两层循环for (i 0; i S; i) { //i是藏宝图横坐标for (j 0; j S; j) { //j是藏宝图纵坐标//遍历到的坐标藏宝图和绿化图表示的不一样则直接break表示以绿化图这棵树为开始不符合要求需要判断其他树//s.first.first表示绿化图中树的横坐标s.first.second表示绿化图中树的纵坐标if (Graph[i][j] ! Tree[{s.first.first i, s.first.second j}]) {flag false;break;}}if (!flag) //跳出两层循环遍历其他树break;}if (i S) //i越界则j一定越界表示以绿化图这棵树为起点满足要求结果res;}}cout res endl;
}
