一、题目
二、分析
因为藏宝图左下角位置一定是一棵树,所以只要把所有绿化图中每一棵树,与之相匹配,然后判断,是否整个藏宝图都是绿化图的一部分,如果是那就计数count+1。所以来看,结果count最大也就是n(绿化图中树的棵数)。
只要注意一下判断藏宝图右上角会出现超出绿化图边界的情况,和懂得如何遍历整个藏宝图去判断是否与绿化图的某一部分一致就ok啦!
三、代码
废话不多说,看妾身代码!
#include <iostream>
using namespace std;
int tree[1005][2];//存放绿化图中树位置坐标
int map[55][55];//藏宝图//判断藏宝图中的一点(l,r)是否在绿化图中有对应的位置匹配
bool isPositionMatching(int l, int r, int x, int y,int n)
{int i;//遍历绿化图中所有树//如果存在与藏宝图中对应的位置,返回真;否则,返回假for (i = 0; i < n; i++){if (tree[i][0] == x + l && tree[i][1] == y + r){return true;}}return false;
}//判断藏宝图是否与绿化图中某一部分一致
bool isTrue(int x, int y, int L, int s, int n)
{//超出范围if (x + s > L || y + s > L){return false;}int i, j, k;//遍历整个藏宝图,比较绿化图for (i = 0; i <= s; i++){for (j = 0; j <= s; j++){//如果是树的话,那么在存放绿化图中树位置坐标的数组tree找不到匹配的点,//该藏宝图一定不会是这一块绿化图的一部分if (map[i][j] == 1){if (isPositionMatching(i, j, x, y, n) == false){return false;}}//如果不是树的话,那么在存放绿化图中树位置坐标的数组tree找到了匹配的点,//该藏宝图一定不会是这一块绿化图的一部分if (map[i][j] == 0){if (isPositionMatching(i, j, x, y, n) == true){return false;}}}}//如果上面的情况都没有出现,那么这就是一个相匹配的位置return true;
}
int main()
{int n, L, s;cin >> n >> L >> s;int i, j;int count = 0;for (i = 0; i < n; i++){cin >> tree[i][0] >> tree[i][1];}for (i = s; i >= 0; i--){for (j = 0; j <= s; j++){cin >> map[i][j];}}//判断for (i = 0; i < n; i++){if (isTrue(tree[i][0], tree[i][1], L, s, n) == true){count++;//符合的就计数+1}}cout << count << endl;
}