CCF 22-06-02 寻宝！大冒险！

题目背景

暑假要到了。可惜由于种种原因，小 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 矩阵 B（S 远小于 L），对应着 A 中的某一部分。
理论上，绿化图 A 中存在着一处坐标 (x,y)（0≤x,y≤L?S）与藏宝图 B 左下角 (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] 一行最后输入。

输出格式

输出到标准输出。

输出一个整数，表示绿化图中有多少处坐标可以与藏宝图左下角对应，即可能埋藏着顿顿的宝藏。

样例一输入

5 100 2
0 0
1 1
2 2
3 3
4 4
0 0 1
0 1 0
1 0 0

样例一输出?

?3

样例一解释

?绿化图上?(0,0)、(1,1)?和?(2,2)?三处均可能埋有宝藏。

样例二输入

5 4?2
0 0
1 1
2 2
3 3
4 4
0 0 0
0 1 0
1 0 0

样例二输出

0?

样例二解释

如果将藏宝图左下角与绿化图?(3,3)?处对应，则藏宝图右上角会超出绿化图边界，对应不成功。

子任务

40%?的测试数据满足：L≤50；

70%?的测试数据满足：L≤2000；

全部的测试数据满足：L≤1000、L≤109?且 S≤50。

提示

实际测试数据中不包括答案为?0?的用例。

解题思路?

? ?首先，分析题目，获取有用的信息，包括概念定义，约束条件，题目要求，样例输入。

很显然，读完题后，感觉是关于数组的题目，尤其是数组中包含大量零元素，让我们首先想到的就是稀疏矩阵。第二点，问题第二段介绍了藏宝图，看起来十分复杂，但画图分析很容易看出这段是在告诉我们藏宝图的尺寸很小，且藏宝图一定在绿化图中，其中题目给出一个不等式帮助我们分析藏宝图是否越界情况。第三点，我们要保证藏宝图与绿化图的对应关系，必须考虑藏宝图的树位置与绿化图是否对应。最后，题目中最重要的一个线索是藏宝图左下角一定是一棵树，即藏宝图对应绿化图左下角的元素一定是1。

代码实现?

import java.util.HashMap;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		HashMap<Integer, Point> map = new HashMap<>();
		int n = sc.nextInt();
		int L = sc.nextInt();
		int S = sc.nextInt();
		// 绿化图
		int[][] greenMap = new int[n][2];
		for (int i = 0; i < n; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			greenMap[i][0] = x;
			greenMap[i][1] = y;
			map.put(i, new Point(x, y));
		}
		// 藏宝图
		int[][] treasureMap = new int[S + 1][S + 1];
		int tree = 0;
		for (int i = S; i >= 0; --i) {
			for (int j = 0; j <= S; j++) {
				treasureMap[i][j] = sc.nextInt();
				if (treasureMap[i][j] == 1) {
					tree++;
				}
			}
		}
		// 可能的位置
		int count = 0;
		for (int i = 0; i < n; i++) {
			// 判断是否越界
			if (greenMap[i][0] < 0 || greenMap[i][0] > L - S || greenMap[i][1] < 0 || greenMap[i][1] > L - S) {
				continue;
			}
			// 判断是否对应藏宝图
			int num = 0;
			int rangeNum = 0;
			if (treasureMap[0][0] == 1) {
				num++;
				rangeNum++;
			} else {
				continue;
			}
			for (int j = 0; j < n; j++) {
				if (j == i) {
					continue;
				}
				int x = map.get(j).x;
				int y = map.get(j).y;
				// 超出范围
				if (x >= greenMap[i][0] && y >= greenMap[i][1] && x - greenMap[i][0] <= S && y - greenMap[i][1] <= S) {
					rangeNum++;
					if (treasureMap[x - greenMap[i][0]][y - greenMap[i][1]] == 1) {
						num++;
					}
				}
			}
			
			if (rangeNum == tree && num == tree) {
				count++;
			}
		}
		sc.close();
		System.out.println(count);
	}
}

class Point {
	int x;
	int y;
	
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

? ? ? 保证用例输入正确的前提下，我们需要想明白的是使用蛮力法从绿化图的左下角开始不断平移，与藏宝图进行匹配；还是使用题目给出的条件——藏宝图左下角一定是树，我们可以排除大量无效的点。很显然，要利用条件，那么我们可以确定外层循环的次数为n，宝藏可能出现的位置不超过n。假设选择第一个树，我们应该判断以第一个树（x，y）为藏宝图的左下角，判断藏宝图是否超出绿化图的边界，题目中给了我们越界条件 (x,y)（0≤x,y≤L?S），我们可以直接拿来判断。接下来，我们要确定藏宝图与绿化图对应位置是否一致，对于左下角，我们确定绿化图对应位置的值一定是1，所以只需要单独判断藏宝图左下角即可。这里我定义了两个变量，num 表示与绿化图对应的树的数量，rangeNum表示范围内出现的树的数量，如果藏宝图左下角是树，那么继续判断其他位置。

? ? ?我使用HashMap结构将所有树都存储了起来，我是怕继续使用循环会让逻辑变得很乱，所以我定义了Point类存储每一个点，这样也方便。内层循环首先判断选择的树是否在藏宝图当中，如果不在没有必要考虑，如果存在，rangeNum++，再判断与藏宝图对应位置的树是否存在，若存在，num++。为什么要考虑rangeNum == tree（藏宝图树的数量）。假设藏宝图与绿化图中树都对应，但你能保证这两张地图是相同的吗，如果对应绿化图不仅包含藏宝图全部的树，还有其他位置也有树，这种情况很显然是不能考虑在内。因而必须保证范围内出现的树的个数与藏宝图实际存在的树的个数一致才行。