XorLife
SRM 541 · 2011-11-22 · by semiexp
SRM 541 · 2011-11-22 · by semiexp · Search, Simulation
Problem Statement
Problem Statement
Magical Girl Madoka just learned about Conway's Game of Life. She is now thinking about new rules for this game.
In the Game of Life, an infinite plane is divided into a grid of unit square cells. At any moment, each cell is either alive or dead. Every second the state of each cell changes according to a fixed rule. In Madoka's version of the game the following rule is used:
You are given theint K and a String[] field that describes the initial state of the plane. field describes only some rectangular area of the plane. More precisely, character j of element i of field is 'o' if the cell in the i-th row of the j-th column of the rectangular area is alive, and it is '.' otherwise. Cells which aren't described in field is initially all dead.
Return the number of alive cells after K seconds.
In the Game of Life, an infinite plane is divided into a grid of unit square cells. At any moment, each cell is either alive or dead. Every second the state of each cell changes according to a fixed rule. In Madoka's version of the game the following rule is used:
- Consider any cell C. Look at the current states of the cell C and all four cells that share a side with C.
- If an odd number of these cells is alive (i.e., 1 cell, 3 cells, or 5 cells), cell C will be alive in the next second. Otherwise, cell C will be dead in the next second.
- Note that each second the rule is applied on all cells at the same time.
You are given the
Return the number of alive cells after K seconds.
Notes
- You can assume that the result will fit into a signed 64-bit integer.
Constraints
- field will contain between 1 and 50 elements, inclusive.
- Each elements of field will contain between 1 and 50 characters, inclusive.
- All elements of field will contain the same number of characters.
- Each character in each element of field will be either 'o' or '.'.
- K will be between 1 and 1,000,000,000, inclusive.
Examples
0)
{"oo"
,"o."}
3
Returns: 23
The status after 3 seconds is below. ...oo... ..oo.o.. .o.oooo. ooooo..o o.oo.... .oo..... ..o..... ...o....
1)
{".."
,".."}
23
Returns: 0
All cells of the plane can be dead.
2)
{"o"}
1234567
Returns: 11018125
3)
{"o.oo.ooo"
,"o.o.o.oo"
,"ooo.oooo"
,"o.o..o.o"
,"o.o..o.o"
,"o..oooo."
,"..o.o.oo"
,"oo.ooo.o"}
987654321
Returns: 447104494375
4)
{".o.", "o..", "..."}
981
Returns: 32550
Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class XorLife with a public method long long countAliveCells(vector<string> field, int K) · 109 test cases · 2 s / 256 MB per case