FloodFill3D

TCO12 Semifinal 1 · 2012-03-27 · by ir5

TCO12 Semifinal 1 · 2012-03-27 · by ir5 · Brute Force, Simple Math

Show categories

Class Name: FloodFill3D

Return Type: long

Method Name: countBlack

Arg Types: (vector<string>, vector<string>, vector<string>)

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.

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

{"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.

{"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.

{"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.

{"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

{"ooxxx"}
{"oooooooooxxxxxxxxxxxxxxxx"}
{"ooooooooxxxxxxxxxxxxxxx"}
Returns: 2011

Submissions are judged against all 62 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FloodFill3D with a public method long long countBlack(vector<string> SArray, vector<string> TArray, vector<string> UArray) · 62 test cases · 2 s / 256 MB per case