back to the menu

 Flag Counter

TopCoder SRM 541 - 1000: XorLife

Problem Statement

     题目简述：

一个无限大平面被划分为由单位方格组成的网格图。
一开始每个方格内的数是1或0。
每秒过后，每个方格内的数 变成他上下左右相邻的、再加上它自己共五个格子 数值的Xor。
输入含有1的那一部分的网格图。
求K秒之后，数值为1的方格有多少个。

数据范围：

输入的网格图大小：n<=50, m<=50
K<=1,000,000,000


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:

  • 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.
Madoka wants to know how many cells are alive after K seconds.



You are given the int K and a vector <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.

Definition

    
Class:XorLife
Method:countAliveCells
Parameters:vector <string>, int
Returns:long long
Method signature:long long countAliveCells(vector <string> field, int K)
(be sure your method is public)

Limits

    
Time limit (s):2.000
Memory limit (MB):64

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

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)2003, TopCoder, Inc. All rights reserved.