Pattern Recognition
TimeLimit:12000MS MemoryLimit:786432KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description
Given an image consisting only lowercase letters, for each query you should count the number of patterns in the image.
Formally, an image is a matrix with $n$ rows and $m$ columns, and each cell of the matrix contains a character. Considering a string consisting of lowercase letters, we can place it horizontally or vertically, so it has following shapes:
We can bend it $90$ degrees, and we get some new shapes:
In a word, a pattern is a string with these $6$ possible shapes:
For example, pattern abcd can have following shapes:
Kanari loves CV(Computer Vision), he writes a CNN(Convolutional Neural Network) to count the number of patterns in an image. Kanari is so cute, and the accuracy tends to $100\%$ after a long time parameter adjustment. Can you solve it too?
Formally, an image is a matrix with $n$ rows and $m$ columns, and each cell of the matrix contains a character. Considering a string consisting of lowercase letters, we can place it horizontally or vertically, so it has following shapes:
We can bend it $90$ degrees, and we get some new shapes:
In a word, a pattern is a string with these $6$ possible shapes:
For example, pattern abcd can have following shapes:
Kanari loves CV(Computer Vision), he writes a CNN(Convolutional Neural Network) to count the number of patterns in an image. Kanari is so cute, and the accuracy tends to $100\%$ after a long time parameter adjustment. Can you solve it too?
Input
This problem contains multiple test cases.
The first line of the input contains an integer $T (1 \leq T \leq 5)$ indicating the number of test cases.
For each test case, the first line contains three integers $n, m, q (n \geq 1, m \geq 1, 1 \leq n \times m \leq 10^5)$, representing the width of the image, the height of the image and the number of queries.
Each of the next $n$ lines contains $m$ characters representing the image.
Each of the next $q$ lines contains a string representing a query.
It is guaranteed that the sum of length of all queries in a test case is no more than $10^5$.
The first line of the input contains an integer $T (1 \leq T \leq 5)$ indicating the number of test cases.
For each test case, the first line contains three integers $n, m, q (n \geq 1, m \geq 1, 1 \leq n \times m \leq 10^5)$, representing the width of the image, the height of the image and the number of queries.
Each of the next $n$ lines contains $m$ characters representing the image.
Each of the next $q$ lines contains a string representing a query.
It is guaranteed that the sum of length of all queries in a test case is no more than $10^5$.
Output
For each query, output the number of corresponding patterns occurred in the image. Note that two occurences are different if and only if the
SET of positions for the pattern in the image are different.
SampleInput
2 10 10 1 xxxxxxxxxx xbcdxxxxxx xaxxxdcbax xxxdxxxxxx xxxcbaxxxx xxxxxxabxx xaxaxxdcxx xbxbxxxxdc xcxcxxxxxb xdxdxxxxxa abcd 5 5 2 xsssx xxbxx xbabx xxbxx xxxxx ab sss
SampleOutput
6
4
1
Hint Explanation for the second testcase: For pattern ab , the occurences are { (2, 3), (3, 3) }, { (3, 2), (3, 3) }, { (3, 3), (3, 4) }, { (3, 3), (4, 3) }. For pattern sss , the only occurence is { (1, 2), (1, 3), (1, 4) }.