HappyCells

SRM 406 · 2008-06-18 · by eleusive

SRM 406 · 2008-06-18 · by eleusive · Simple Search, Iteration

Show categories

Class Name: HappyCells

Return Type: int[]

Method Name: getHappy

Arg Types: (vector<string>)

Problem Statement

Consider a rectangular grid of cells that is given by a String[] grid. A cell marked with a 'X' character denotes an occupied cell, and a cell marked with a '.' character denotes an empty cell. We say that two cells are orthogonal neighbors if they share a common side, and they are diagonal neighbors if they are adjacent to one another diagonally.

We say that a cell is 1-happy if the cell is empty and all of the cell's orthogonal and diagonal neighbors are occupied (note that a cell may have fewer than 8 neighbors). A cell is 2-happy if the cell is empty and all of the cell's orthogonal neighbors are occupied, but one or more of its diagonal neighbors are empty. A cell is 3-happy if the cell is empty and all of the cell's diagonal neighbors are occupied, but one or more of its orthogonal neighbors are empty.

Return a int[] with 3 elements. The first element should be the number of 1-happy cells, the second element should be the number of 2-happy cells, and the third element should be the number of 3-happy cells.

Constraints

grid will contain between 1 and 50 elements, inclusive.
Each element of grid will contain between 1 and 50 characters, inclusive.
Each element of grid will contain the same number of characters.
Each character in grid will be either an uppercase 'X' or '.'

Examples

{
"XXX",
"X.X",
"XXX"
}
Returns: {1, 0, 0 }

The center cell is 1-happy.

{"X"}
Returns: {0, 0, 0 }

{"."}
Returns: {1, 0, 0 }

Note that even though this cell has no neighbors, it is 1-happy because there are no neighbors to be empty.

{"....XX.XX......XXXXX.XXXXX..X.XX.XXXX.X.X.XXX..XX.","XX.X...X..XXX.XX.X.X......X.XX.X....X.XX..X.....XX","X.X..X.XX...X...XXXX..XX.X..XX....XX.XX.X...X.X.X.","..XX..X.XXX.XXXX..X.X.X...XXX.X..XX....X.XX..X....","..XXX..XXXXX.X..XXX...XXX...X..XXX.X....X....X..X.","XX.XXX.X...X...X...XX..........XX..X..X...XX.X..XX","XX.XX.X.X...XX.XX....X...XXX..XX.X..X.XXX.X...XXX.","...XXXX......X..XX.XX.X..XXXX.XX.X..X.X.XXX.X.X.X.","..XX.XX.X.XX.X.X....X..X.XX..X..XXXX.X.XX.....XX.X","X...X....X....X..XXX.X.XX....XXX.X..XXXX..XXXX.X..",".XX.XXX.......X.X...X.XXXXX....X.XX..X..X.X...XX..","..X..XX..XXX.X..XXXX.X..X.XX.X...X.X.X.X..X..XX.X.","X.XXX..XX.XX.X..X.X.X...X.X.X.XXX..XX..X.X..XXX..X","XXXXXX.XXX...XX.XXX..XXXXXXXX..X......XXX.XXX.....","X..X.XXX...XX.X...X...X.XXXXX..X....XX.XX.X....X.X","..X.X....X...XXX...XXXXX...XX.X..XXX.XX..X...X.XX.",".....X.XX.XXX..XXX..XXX..X.X.XXXXXX...X..XXXXXXX.X","X...XX.XX.X...X.XX.XX.XXXX.XXX.X..X.XXXXXX........","..X.X.XX....X....XX.XX.X.XX.XX...XXXXXX.....XX.X..","XXX...X..XXX.X.XX.X.X.XXX...X..XX........XX..XX...",".XX.XXXX.X.....X.XXXXX.XX..X.X.XXXX.XX.XXX..XXXX..","XXX...XXXXXXX..XXX.X.XXX.X...X.X.XXX.X..X.X..X.XX.",".XXX.XX.X.XXXX.XX.XXXXX.XX....X.XX..X.X..X.X.....X","XX.XXXX.X......X..X...X....X..X....XXX..X..XX..X..","XX..X.X.X..X.XX..X...X..XX.X.X.XXX.X.XX.XXX.X....X",".X.X....XXX...X....XXX........XX.XX.XX..XXX.X.....","X....XXX.XXX.X.XX.XX.X.X...XXX......XX.XX.XXX..XXX",".X.X..XX..XX..X.X....XX.XXXXX..X...X.XXXXX.XX..XXX",".XXXXXX.X.XX.XXXXX....XX.X.XXX.X..X..XX.X..XXX.X..","..X...XX.XXX.X...X.X..XX.X.X.XXXXX.X.X.XXXXXX..XXX","X.X..X.X.XX.XXX...XX.XX..XXXXXXX..XXX.X..XXXXXXX.X","X..XXX.X.X.X..X..XXXX.XXX.XXXX...XXXXXXX.X.X.X...X","X...XXX...XXXX..X.XX......X.X.X.X.X..XXXXX......X.",".X..XX....X.X.XX.XX.XX...X.XXX.X....X.....X.XX..X.","X..XX.XXX...X....X..X..XX.X.XXXX.XX.XX.XXXX......X","XX..X.XXXX....XX..XX.XX..........XX...XXXX....X.X.",".......XXXXX..XXX....X.X...X.....X.X.X.XXXX..XX..X","........X.XX.....X..XX...XX...XXXXX.XX.XX.X.XXX..X","X.XXXXXX....XXXX.XXXXX....X.X...XX.......X...X.X.X",".X...XXX..X.XXXX..X.XXX..XX.XXX.X...X.....XXX..XX.","X.X..XXXX...XXX..X...X.......XXXX.X.X.XXXXXXXXX..X","....X.X......XX.X.XX..X.X.X.XX..X..X.X...XX..XXXXX","X.XXXX..XXX.X.XXXXXXX.X.X.XX.XX.XX.X.X.XX....X..X.",".XXXX......XXX.X..X....X....X.XX...X..X...XXXX..XX",".XXX..XXXXX..XXX...XX...X.X..XX...XX.X..X..X..XXX.","X.XX.XX..XXXXX.X.XXXXX.X...XX..X.XXX...XX.X.XX...X","..XX..XXXXXX.X.XXXX...X.X.XXXXXXXX..XX.XXXX.X.XXX.",".XXX....X..X..XX......X...X.X.....XXX..X.XX...X...","...X..XX..XX.XXXX..X.XX.X.X.X..X.X........XXXXXXXX","XXXX.X..XXXX.X.X.X..X.X.XXX...X.XXXXXXX.X..XXXX..."}
Returns: {9, 72, 83 }

{"...X..XXX..X.X...X.....XX..X.X.XX..XXXXXXX..XXX.X.","X.XX.XXXXX........X.XX.X..X..XXXXX....X.....XXX.X.",".XXXX..X.X...XX.XX.XXX..X.X.X.X.X.X.X..X.XXX..XXX.","XX..X.XX.XX....X..XX....XX..XXXXX.XX..XXX.X.....XX","XX...XX.....X..X..XX.X..XX...X.XXXX....XX.XX.XX...","...XX...X...XX.X...X.X.X...XX.XX..XXX..XXXX..XX.XX","X.XX.......X.XX..XXXXX.XXXX..X.X.X..XX..XX.X..X..X",".XX..XX.X.....X.X.XXXX.XX.X.XX.XX.X.....X..XXX....",".XX.X.XX.X.X..X..XX..XXX..XXXXX...XX.....XXXX.XX.X","XX.XX.XXX.X.X.XXXX.X.XX.XX.....X.XXX...X.....X..XX",".X..X.X.XXXXXX..X.X.XXX..X......XXX....XXX.XX.XXX.","XXXX...X.X.X.XXX..X.X...XXXX.....XX.XXX.X..XXXXXXX",".XX.XX.XX......XX...X.X.X..X....X..X.X.X.XXXX.XXXX","X....XX.X....XXX.....XX.XX..XX.X..XXX.XX.XXX....XX",".X.X.XXX....X.XX.X.X.X...XX.X..X......X....XXX..XX","X...X..X.XX..XXX.XXXX.......XX.XX......X....X...X.",".X.XX.XX..XX.X....XX.X..XXXX.X.......XXXX.XX.X..X.","....X.XX.XX..XX..XXX..X....X.........XX.XXXX.X.X.X","X.XX...X...XX.X..XXXX..XX.X..X.X...X...X..XXX....X",".XXXX.......X.XXXXX..X..XXXXXX..XX.XXX.X....XXXXX.","XX.XXX..X..X.XX.XX.X.......X...XXXX..XXX.X.X.X..XX","XXX..XX.XX.X.X.XX.X..X.XXXX.....X.X....XXX....XX..","..XX..X..X.X.XXXXX.XX.X..X.X.....XX.X.XX..XXX.X..X","X.XXX...XXX..X....XXX.XXX.XXX..X.XX.XX.XXXXXX..X..","XXX.X..X.XX...X.X.X.X...X.XXXX.X...XXXX..X.XX.....","X.XXXX.X.X..X....X....XXX.X.X.X..XX..XXX...XX.X..X","X.X.X.X...X..X.X.XXX...XX...X..XXX.XX...X.XXXXXXXX","XXXX..XXXX...X.....XXXXX.XX.XX..X.X...XX.X..XX....","XX..XXX.X.X.X.X.XXX...XXX.X..X....XXXXX..XXX.XXXX.","..XX.XX...XX.XX.XXXXXXXXXXXXX..XX....X..X.X..XXX.X","X......X..X..X.XX.X..XX...XXXX..X.XXX.X.X..X...X.X","XXX..XX...XXXXXX.XX..X..X.XXXXXXX.XX....XX.X.XXXXX","X.X.X..XX.X..X.XXXX.XX.XX..XX..XX.X.X.XXX..XX..X..","X..XXXXXXXXX.X...XX....XXX..X.X.XX.X....X.XX.XX..X","...XXXXXX..X.X...X...XX.X..X..X....X.X..X.X.X..X.X","...XXXXX......X..XXX.XXX.XXXXXX...X.X....X.X......","X.X..X.XXX.X.....X..XXX..XXX....X.....XXX.X.X.XXX.",".X......X.XXX.X.XXX.XX.X.XXXX.X.XX.X.XXX.X.XX....X","..XXX..X.X.X.X.X...X..XX....X.....X..XXXX.X.XXXX..","X..XXXX.XX..........XXX...X...XX.......XX......X..",".XX..X.X.X.XX......X.X...X.X.XXX.X..XXX.X..XX....X","XXX....XX.....X.XXX.XX...X.X.XX..X.X..XXXX..X...X.",".XX......X...XXX....XX.X.X..X.X...XX..XX.X.XXX..XX",".XX..X.X.X...X.XX..XX.X.X.XX.XXX.X......XX..XXX...","X...X...XXXXX.XX.XXX.XXX..XX.X.....XX.X.XX.X......","XXX.X.XX.X..X.X..XX.....X.XX...X.X.X.XXX..XX.XX..X","..X.X..XX..XXX.X...XX.X.X..XXX..X.XX...X.XX.....XX","XX.X.XX.X.XX....XXX.XX.X.X.XXXX.X......XXXX..X...X","XX.X...XX..XXX...XX....X..X...X.XXX.XX.XXX.X......","XX....XX.X..XX...XXX.X....XXX.XX.XXX.XXX.X.XXXX..X"}
Returns: {6, 69, 79 }

{
"XXXXXX",
"X.XXXX",
"XXX.XX",
"X..XXX",
"XXXXXX"
}
Returns: {1, 1, 1 }

The uppermost empty cell is 1-happy, the empty cell on the third row is 2-happy, and the left cell on the fourth row is 3-happy. Note that the right cell on the fourth row is not happy because it has both diagonal and orthogonal neighbors that are empty.

67)

{"..."}
Returns: {0, 0, 3 }

Note that with no diagonal neighbors, there are no diagonal neighbors to be empty. Thus, each cell is 3-happy.

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

Coding Area

Language: C++17 · define a public class HappyCells with a public method vector<int> getHappy(vector<string> grid) · 89 test cases · 2 s / 256 MB per case