20240623
有一天,超能侠获得了一张神秘的藏宝图。藏宝图可以视作一个大小为(L+1)*(L+1)的01矩阵A,左下角坐标为(0,0),右上角坐标为(L,L)。图上标出了n个点位,用1来表示。传说,冒险家的宝藏就埋在n个点位之一的地下。也就是说,矩阵中有且仅有n个1,展示出了宝藏的n个可能位置。
超能侠决定出发寻找宝藏,但n个位置一个一个找起来需要很长时间,于是他请占星术士帮忙,进一步缩小了宝藏可能的位置。具体而言,占星术士帮助他找出了藏宝图中的一小块,即从藏宝图中得到了一个大小为(S+1)*(S+1)的01矩阵B,称为“预言图”。预言图的左下角B[0][0]一定为1,标识了宝藏埋藏的位置。
但占星术士能力有限,该预言图可能与藏宝图中的多个位置相匹配,即对B上的任意一处坐标(i,j),都有多个A中的(x,y)满足A[x+i][y+i]=B[i][j]。请你结合藏宝图和预言图,判断有多少处位置满足条件。
输入文件第一行给出三个整数n,L和S,分别表示点位数,藏宝图的大小,预言图的大小。
接下来n行,每行两个整数x和y,表示藏宝图中点位的坐标。
接下来S+1行输入完整的预言图,其中第i行包含S+1个0和1。注意最先输入的是B[S][0]...B[S][S]这一行。
输出文件只有一行一个整数,表示藏宝图中有多少处可以与预言图对应,即可能埋藏着宝藏。
输入
5 100 2 0 0 1 1 2 2 3 3 4 4 0 0 1 0 1 0 1 0 0
输出
3
输入
5 4 2 0 0 1 1 2 2 3 3 4 4 0 0 0 0 1 0 1 0 0
输出
0
【输入输出样例1说明】
藏宝图中的(0,0),(1,1),(2,2)三处均可能埋有宝藏。
【输入输出样例2说明】
找不到对应的位置,如果将预言图左下角与藏宝图中的(3,3)处对应,则预言图右上角会超出藏宝图边界,对应不成功。
对于40%的数据,2≤L≤50;
对于100%的数据,2≤n≤1000,2≤L≤2000,1≤S≤50,始终保证S<L,n≤(L+1)*(L+1)。
(思考:若L≤10^9,应该如何处理?)