题目描述
给一个稀疏大图,一个稠密小图,求匹配个数
分析思考
稠密图用pair数组存出现1的坐标,稀疏图直接二维数组存!
考虑到藏宝图较小,我们直接枚举!
遍历所有大图中的树,我们先考虑用其第中m[i]棵树对其藏宝图左下角
边界条件:若对其后超出边界,直接跳过
筛选其他在范围内的树,如果都在藏宝图内位置为1,并且数量一致,总数++;
算法1
(模拟枚举) $O(n*s^2)$
//这里填你的代码^^
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,L,s;
#define x first
#define y second
typedef pair<int, int> PII;
PII m[2010];//big map
int p[100][100];
int main()
{
cin>>n>>L>>s;
int count=0;//avaliable choices
int k=0;//trees in treasure map
for (int i = 0; i < n; i ++ ){
cin>>m[i].x>>m[i].y;
}
for (int i = s; i >= 0; i -- ){
for (int j = 0; j <= s; j ++ ){
cin >> p[i][j];
if(p[i][j]==1)k++;
}
}
//cout << p[2][2]<<endl;
//cout << k<<endl;;
for (int i = 0; i < n; i ++ ){
int cnt=0;
int number=0;
if(m[i].x+s>L||m[i].y+s>L)continue;
for (int j = 0; j < n; j ++ ){
if(m[j].x-m[i].x<=s&&m[j].x>=m[i].x && m[j].y-m[i].y<=s&&m[j].y>=m[i].y ){
//cout << m[j].x<<' '<<m[j].y<<endl;
number++;
if(p[m[j].x-m[i].x][m[j].y-m[i].y]==1) cnt++;
}
}
//cout << m[i].x<<' '<<m[i].y<<' '<<cnt<<' '<<number<<endl;
if(number!=k)continue;
if(cnt==k)count++;
}//go all trees
cout<<count;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~