Connection Status:
Competition Arena > NonXorLife

NonXorLife

SRM 541 · 2011-11-22 · by semiexp

SRM 541 · 2011-11-22 · by semiexp · Simulation
Class Name: NonXorLife
Return Type: int
Method Name: countAliveCells
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

Magical Girl Sayaka 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 Sayaka'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 at least one of these five cells are alive, 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.
Sayaka wants to know how many cells are alive after K seconds.

You are given the int 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.

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 1500, inclusive.
Examples
0)
{"oo"
,"o."}
3
Returns: 36

The status after 3 seconds is below. ...oo... ..oooo.. .oooooo. oooooooo ooooooo. .ooooo.. ..ooo... ...o....

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

All cells of the plane can be dead.

2)
{"o"}
1000
Returns: 2002001
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"}
1234
Returns: 3082590
4)
{"oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo","oooooooooooooooooooooooooooooooooooooooooooooooooo"}
1500
Returns: 4799500

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

Coding Area

Language: C++17 · define a public class NonXorLife with a public method int countAliveCells(vector<string> field, int K) · 102 test cases · 2 s / 256 MB per case

Submitting as anonymous