200270 - 模板匹配技巧
我们学习过模板匹配,解决这类问题秉承的思路是逐行逐列与模板对照,为了降低编程难度,我们通常把检测模板和从当前位置开始的和模板同样大小的区域这一过程写成函数。
请你在一个n行m列只包含小写字母的矩阵中,找出2×2的方格中有多少个同时包含"face"这4个字母的。
提示:
按照直接的思路,我们需要在模板匹配过程中判断4个字母各1个,这会写很多判断语句;通常,我们把模板定义成一个(多个)数组来解决问题,这是解决模板匹配的根本做法。但像本题这种情况——模板较小且不要求顺序,我们可以采用进阶一点的方法:设计一组掩码来简化模板匹配函数:
把face这4个字符分别记为1、2、4、8,其他均为0;之所以这样定义是因为无论怎么组合4个字母,只有各1个的时候总和为15。这种定义可以用一个arr[128]来实现。
思考:
如果是判断look该如何设计映射关系?
其他=0,l=1,o=2,k=4是否可行?
其他=0,l=1,k=2,o=4是否可行?
设计技巧是什么?
Input
一行,两个整数n,m,分别表示行数和列数。
对于100%的数据:
1\le n,m \le 50 。
字符只包含小写字母。
Output
Examples
Input
2 3 fac cef
Output
2