50002. Game of Life

I'm a slow walker, but I never walk backwards.

Problem description

The Game of Life is a two-dimensional $n$ by $n$ grids, each of which is in one of two possible states, alive or dead. Every cell interacts with its up to eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

  • Any live cell with fewer than two live neighbors dies.
  • Any live cell with two or three live neighbors lives on to the next step.
  • Any live cell with more than three live neighbors dies.
  • Any dead cell with exactly three live neighbors becomes a live cell.

Now given the initial configuration of the grids, please simulate the game for $k$ steps, and report the final configuration and the cell that has been alive for the maximum number of times. For example, if we simulate $k$ steps then a cell can be alive up to $k + 1$ times. If there are multiple of them, report the one that has the largest row index. If there are still multiple answers in that row, report the one that has the largest column index. For example, if we have [2][3], [2][5], and [3][1], [3][2] as answers, we report 3 2.

Technical Specification and constraints

  • 10pt. $k$ is $0$, and $n$ is between 1 and 10.
  • 10pt. $k$ is $1$, that is, you only need to simulate a single step, every cell is alive initially, and $n$ is between 1 and 10.
  • 50pt. $k$ is $1$, and $n$ is between 1 and 100.
  • 30pt. $k$ is between 2 and 10, and $n$ is between 1 and 100.

Sample Input 1

5 0
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0

Sample Output 1

0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
3 2

Sample Input 2

5 1
1 0 0 0 1
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
0 1 0 1 0

Sample Output 2

0 0 0 0 0
0 0 1 0 0
0 1 0 1 0
0 0 0 0 0
0 0 1 0 0
3 4

Sample Input 3

5 3
1 0 0 0 1
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
0 1 0 1 0

Sample Output 3

0 0 0 0 0
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0
0 0 0 0 0
3 4

Hint

Since we need the old status to compute the new status, it is much convenient that we store the old status in one array A, the new status in another array B, and compute B from A in the first step. Then in the second time step we compute A from B.

Discussion