JOIN
Get Time

   Problem Statement  

 Problem Statement for FloodFill3D

Problem Statement

    There is a 3-dimensional grid that consists of N*M*L cells. Each of the cells has three integer coordinates (i,j,k), where 0 <= i < N, 0 <= j < M, and 0 <= k < L. Initially, the cells are colorless. You are now going to color each of the cells either white or black.

You will be given three strings: S, T, and U. Each of these strings only contains the characters 'o' and 'x'. The lengths of these strings are N, M, and L, respectively.

The coloring of cells will consist of two steps. The first step looks as follows: For each i,j,k: you color the cell (i,j,k) white if the three characters S[i], T[j], and U[k] are all the same. Otherwise, you color the cell black.

Once the first step is done, the white cells will form some connected components. (Two cells belong to the same component if they share a common face. Belonging to the same component is transitive.) A white component is said to be on the boundary, if at least one of its cells has a face that is on the boundary of the grid.

In the second step, the white components that are on the boundary will remain white, and the color of all remaining white components is changed to black.

You are given three String[]s: SArray, TArray, and UArray. Concatenate all elements of SArray to get S. In the same way, TArray yields T and UArray yields U. Your method must return the number of black cells after the second step.
 

Definition

    
Class:FloodFill3D
Method:countBlack
Parameters:String[], String[], String[]
Returns:long
Method signature:long countBlack(String[] SArray, String[] TArray, String[] UArray)
(be sure your method is public)
    
 

Constraints

-SArray, TArray and UArray will each contain between 1 and 50 elements, inclusive.
-Each element of SArray, TArray and UArray will contain between 1 and 50 elements, inclusive.
-Each character of SArray, TArray and UArray will be either 'o' or 'x'.
 

Examples

0)
    
{"oxo"}
{"oxo"}
{"oxo"}
Returns: 19
The figure below shows how the coloring is done. After the first step, 9 cells are white and the other 18 are black. In the second step, the cell (1,1,1) changes color to black. So there are 18+1 = 19 black cells after the second step.



1)
    
{"ooo"}
{"oo"}
{"o"}
Returns: 0
There are 3*2*1=6 cells and all of those are colored in white in the first step. Since this connected component shares at least one face with the boundary of the cells, it is not recolored. Therefore, the resulting number of black cells are 0.
2)
    
{"xxo", "oox", "o"}
{"x", "o", "x", "o"}
{"ooo", "xxxoo", "oxx"}
Returns: 242
Do not forget to concatenate all elements of the String[]s to get S, T, and U.
3)
    
{"xxxxxxxxxxxxxxxxxxxx"
,"xxooooooooooooooooxx"
,"xxooooooooooooooooxx"
,"xxxxxxxxooooxxxxxxxx"
,"xxxxxxxxooooxxxxxxxx"
,"xxxxxxxxooooxxxxxxxx"
,"xxxxxxxxooooxxxxxxxx"
,"xxxxxxxxooooxxxxxxxx"
,"xxxxxxxxooooxxxxxxxx"
,"xxxxxxxxooooxxxxxxxx"
,"xxxxxxxxooooxxxxxxxx"
,"xxxxxxxxooooxxxxxxxx"
,"xxxxxxxxooooxxxxxxxx"
,"xxxxxxxxxxxxxxxxxxxx"}
{"xxxxxxxxxxxxxxxxxxxx"
,"xxxxxxxoooooooxxxxxx"
,"xxxxxoooooooooooxxxx"
,"xxxxooooooooooooxxxx"
,"xxxxooooxxxxxoooxxxx"
,"xxxxoooxxxxxxxxxxxxx"
,"xxxxoooxxxxxxxxxxxxx"
,"xxxxoooxxxxxxxxxxxxx"
,"xxxxooooxxxxoooxxxxx"
,"xxxxoooooooooooxxxxx"
,"xxxxxooooooooooxxxxx"
,"xxxxxxoooooooxxxxxxx"
,"xxxxxxxxxxxxxxxxxxxx"}
{"xxxxxxxxxxxxxxxxxxxx"
,"xxxxxxxoooooxxxxxxxx"
,"xxxxoooooooooooxxxxx"
,"xxoooooooooooooooxxx"
,"xxoooooxxxxxoooooxxx"
,"xxooooxxxxxxxooooxxx"
,"xxooooxxxxxxxooooxxx"
,"xxooooxxxxxxxooooxxx"
,"xxooooxxxxxxxooooxxx"
,"xxoooooxxxxxoooooxxx"
,"xxxxoooooooooooxxxxx"
,"xxxxxxxoooooxxxxxxxx"
,"xxxxxxxxxxxxxxxxxxxx"}
Returns: 15027148

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2012 TCO Algorithm Semifinal 1 - Division I, Level One