1946. 实验箱之谜

时间限制 2000 ms   内存限制 256 MB

从前有一群计科僧,有一门课叫《汇编与接口》(也叫《微机与接口》)。由于经年的实验,实验室的实验箱出现了不同程度的损坏。

在本学期实验课开课前,老师叫助教小明将所有的实验箱检查一遍,并统计还能正常使用的实验箱数量。

小明用天顶星科技将每个试验箱扫描映射为ASCII中的可见字符(包括空格),形成一个 $n \times m$ 的字符矩阵 $g$ ,形如

##########
#TPC-ZK-2#
#this is #
#a expbox#
##########

可是小明没时间一个一个检查实验箱辣!所以请会编程的你来帮忙检查统计能正常使用的实验箱数量。

现在以字符矩阵的形式给你一个完好的实验箱,和若干需要检验的实验箱。你需要求出有多少实验箱是可以正常使用的。

定义两个字符矩阵 $g,h$ 之间的差异距离如下: $$ \operatorname{diffdist}(g,h)=\sum_{i=1}^n\sum_{j=1}^m\operatorname{diff}(g_{i,j},h_{i,j}) $$ 其中 $\operatorname{diff}(x,y)$ 表示:当 $x,y$ 都是字母时,忽略大小写,计算它们字典序差的绝对值,如 $\operatorname{diff}('a', 'A')=0$。

否则,$\operatorname{diff}(x,y)$为 $x,y$ 两字符的ASCII码差的绝对值,$\operatorname{diff}(x,y)=|\operatorname{ASCII}(x)-\operatorname{ASCII}(y)|$。

我们认为如果 $\operatorname{diffdist}(g0,g) \le r$ (其中 $g0$ 为完好的实验箱),那么实验箱 $g$ 是能正常使用的。

输入数据

第一行为 $2$ 个正整数 $n,m(1 \le n,m \le 100)$ ,表示实验箱对应字符矩阵的高度和宽度。
接下来一共 $n$ 行,为一个 $n\times m$ 的字符矩阵,表示完好的实验箱的形状。
接下来一行一个整数 $p (1 \le p \le 500) $ ,表示将要检测的实验箱个数。
接下来一共 $p\times (n+1)$ 行,其中 $((n+1)\times (i-1)+1) \sim ((n+1)\times i-1)$ 行表示第 $i$ 个将要检测的实验箱的 $n\times m$ 字符矩阵,第 $(n+1)\times i$ 行为一个空行,将前后两个实验箱隔开
最后一行一个整数 $r(1 \le r \le 10^{7})$,表示可以容忍的差值上限。

输出数据

输出一个整数,表示检查得到的能正常使用的实验箱数量。

样例输入

复制
5 10
##########
#TPC-ZK-2#
#this is #
#a expbox#
##########
2
****##**##
*SCIT ACM*
*%%%%%%%%#
*tql  tql#
**##*#####

***#**#***
*this is *
#a prime *
*19260817*
*##*##**##

1000 ·  \n
          \n
          \n
     ·  · \n
  ·       \n
          \n
 \n
          \n
     ·    \n
          \n
    ··    \n
          \n
\n
          \n
     ·  · \n
  ·     · \n
          \n
          \n
\n
    \n

样例输出

复制
1 \n

样例说明

第 $1$ 个实验箱的差异距离为 $1022$ ,不能正常使用;
第 $2$ 个实验箱的差异距离为 $964$ ,可以正常使用;
因此还能正常使用的实验箱有 $1$ 个。

提交

请先 登录

© 2024 FAQs Contact About