Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Time Limit: 3000MSMemory Limit: 65536K
Total Submissions: 6248Accepted: 1239


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.


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.


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


3 3 2 2 2


0 0 0 0 0

Sample Output

Case 1: 1
Case 2: 2


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator