Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3110
Geophysics Prospection

Time Limit: 1 Second      Memory Limit: 32768 KB

The geophysics prospection is a tool that permits to predict the subsoil characteristics, working at variable deeps with multiple targets such as rock differentiation, identification of freatic surfaces and identification of contaminated areas.

A Geo-exploitation company determines the capacity of exploitation of a terrain in terms of the analysis of geophysics prospection of a sample of m adjacent longitudinal layers. Each layer is represented by a matrix of p x k materials.

Materials are identified by a code. The set of layers form a three-dimensional matrix that models the characteristics of the subsoil studied. The problem is to identify the grouping patterns of a same exploitable material. A group of material is that which is contained in adjacent boxes of the layer matrix. Two boxes are adjacent if they share four sides in common.

The material codes and their meaning are described in the following table.

Code Meaning
a A mix of sad and gravel
b Clay
c Mineral
d Gravel
* Material without interest

Input

There will be multiple datasets separated by a blank line. Each dataset consist of two parts. The first part is a line with three positive integers to define the matrix dimensions: p (2 <=p <= 50), space, k (2<=k<=50), space, m (2<=m<=50).

The second part contains the m layers separated by a blank line. Each layer consists of p lines and each line contains k characters representing material codes.

Output

The output consists of the grouping pattern of each dataset separated by a blank line. For each dataset, a line with: the string Case, a space, an integer representing the progressive number of dataset (start counting at one), and an ending colon. The next four lines correspond to the materials with exploitation interest, with the same order that they appear in the input. Each line consists of a character that represents a material code, followed by a variable number of integers that correspond to the elements of identified groups, in descending order. All data in the line are separated by a space.

Sample Input

5 6 2
*a***c
**aa*c
***aa*
cbb*ad
*bb*a*

a****c
a**a*c
***aa*
*b**a*
*b****

4 6 3
*a***c
**aa*c
***aa*
cbb*ad

a****c
a**a*c
***aa*
*b**a*

a****c
a**a*c
***aa*
*b**ad

Sample Output

Case 1:
a 10 2 1
b 6
c 4 1
d 1

Case 2:
a 13 4 1
b 4
c 6 1
d 1 1


Source: The 2007 ACM Mexico and Central America Programming Contest
Submit    Status