题目背景
暑假要到了。可惜由于种种原因，小 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] 一行最后输入。
输出格式
输出到标准输出。
输出一个整数，表示绿化图中有多少处坐标可以与藏宝图左下角对应，即可能埋藏着顿顿的宝藏。
样例 1 输入
1. 5 100 2 2. 0 0 3. 1 1 4. 2 2 5. 3 3 6. 4 4 7. 0 0 1 8. 0 1 0 9. 1 0 0
Data
样例 1 输出
3
Data
样例 1 解释
绿化图上 (0,0)、(1,1) 和 (2,2) 三处均可能埋有宝藏。
样例 2 输入
1. 5 4 2 2. 0 0 3. 1 1 4. 2 2 5. 3 3 6. 4 4 7. 0 0 0 8. 0 1 0 9. 1 0 0
Data
样例 2 输出
0
Data
样例 2 解释
如果将藏宝图左下角与绿化图 (3,3) 处对应，则藏宝图右上角会超出绿化图边界，对应不成功。
思路一
使用直接模拟方法，设计一个巨大的地图map1用来存放所有地图，给地图中的树标记为1。先行遍历所有的树，在每一次遍历中对比藏宝图，检查是否符合条件。
代码
1. 2. n,L,S=map(int,input().split()) 3. map1=[[0 for _ in range(L+1)] for _ in range(L+1)] 4. 5. begin=[] 6. for i in range(n): 7. x,y=map(int,input().split()) 8. begin.append((x,y)) 9. map1[x][y]=1 10. 11. 12. map2=[] 13. for i in range(S+1): 14. map2.append([int(i) for i in input().split()]) 15. 16. map2.reverse() 17. 18. cnt=0 19. for x,y in begin: 20. flag=0 21. for i in range(S+1): 22. for j in range(S+1): 23. if x+i>L or y+j>L: 24. flag=1 25. elif map1[x+i][y+j]==map2[i][j]: 26. continue 27. else: 28. flag=1 29. break 30. if flag==1: 31. break 32. if flag==1: 33. continue 34. else: 35. cnt+=1 36. 37. print(cnt)
缺陷
因为这种方法设计了一个极大的矩阵，题目中所给的数据过大的话就会造成内存溢出，只能过70%的数据
思路2
思路2在思路一之上做出改进，使用字典存储最大的地图，这样可以有效减少内存的使用。因为存储方式的改变，所以我们循环判断的判断条件也要做出更改。思路一的判断条件为
1. if x+i>L or y+j>L: 2. flag=1 3. elif map1[x+i][y+j]==map2[i][j]: 4. continue 5. else: 6. flag=1 7. break
但我们这里没有map1了，为了解决这个问题，我们要改成这样
1. if x+i>L or y+j>L: 2. flag=1 3. if map2[i][j]: 4. if (x+i,y+j) not in map1: 5. flag=1 6. break 7. else : 8. if (x+i,y+j) in map1: 9. flag=1 10. break
这样就可以有效判断藏宝图和大地图是否符合了。
代码
1. 2. n,L,S=map(int,input().split()) 3. 4. #设计存放树的字典，存放大地图 5. map1={} 6. begin=[] 7. for i in range(n): 8. x,y=map(int,input().split()) 9. begin.append((x,y)) 10. map1[(x,y)]=1 11. 12. #藏宝图 13. map2=[] 14. for i in range(S+1): 15. map2.append([int(i) for i in input().split()]) 16. 17. map2.reverse() 18. 19. cnt=0 20. #遍历所有的树 21. for x,y in begin: 22. flag=0 23. #对比藏宝图 24. for i in range(S+1): 25. for j in range(S+1): 26. if x+i>L or y+j>L: 27. flag=1 28. if map2[i][j]: 29. if (x+i,y+j) not in map1: 30. flag=1 31. break 32. else : 33. if (x+i,y+j) in map1: 34. flag=1 35. break 36. if flag==1: 37. break 38. if flag==1: 39. continue 40. else: 41. cnt+=1 42. 43. print(cnt)
