| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1100
Constellations
Time Limit: 2000ms
Memory Limit: 65536kb Description
The starry sky in the summer night is one of the most beautiful things on this planet. People imagine that some groups of stars in the sky form so-called constellations. Formally a constellation is a group of stars that are connected together to form a figure or picture. Some well-known constellations contain striking and familiar patterns of bright stars. Examples are Orion (containing a figure of a hunter), Leo (containing bright stars outlining the form of a lion), Scorpius (a scorpion), and Crux (a cross).In this problem, you are to find occurrences of given constellations in a starry sky. For the sake of simplicity, the starry sky is given as a N × M matrix, each cell of which is a '*' or '0' indicating a star in the corresponding position or no star, respectively. Several constellations are given as a group of T P × Q matrices. You are to report how many constellations appear in the starry sky. Note that a constellation appears in the sky if and only the corresponding P × Q matrix exactly matches some P × Q sub-matrix in the N × M matrix. Input
The input consists of multiple test cases. Each test case starts with a line containing five integers N, M, T, P and Q(1 ≤ N, M ≤ 1000, 1 ≤ T ≤ 100, 1 ≤ P, Q ≤ 50).The following N lines describe the N × M matrix, each of which contains M characters '*' or '0'. The last part of the test case describe T constellations, each of which takes P lines in the same format as the matrix describing the sky. There is a blank line preceding each constellation. The last test case is followed by a line containing five zeros. Output
For each test case, print a line containing the test case number( beginning with 1) followed by the number of constellations appearing in the sky.
Sample Input
3 3 2 2 2 *00 0** *00 ** 00 *0 ** 3 3 2 2 2 *00 0** *00 ** 00 *0 0* 0 0 0 0 0 Sample Output
Case 1: 1 Case 2: 2 Source
2008 Asia Regional, Hefei, Preliminary
|