CCC '06 S5 - Origin of Life

View as PDF
Submit solution
Points: 15
Time limit: 0.5s
Memory limit: 256M
Problem types
Canadian Computing Competition: 2006 Stage 1, Senior #5

Conway's Game of Life is not really a game, but a cellular automaton — a set of rules describing interactions among adjacent cells on a grid. In our game, we have an n by m rectangular grid of cells identified by integer coordinates (x, y).

The game progresses through a series of steps; at each step, a new generation is computed from the current generation. The game begins with the first generation. In any given generation, which we shall call the current generation, each cell is either live or dead. In the next generation, each cell's status may change, depending on the status of its immediate neighbours in the current generation. Two distinct cells (x_1, y_1) and (x_2, y_2) are immediate neighbours if they are horizontally, vertically, or diagonally adjacent; that is, if |x_1 - x_2| \le 1 and |y_1 - y_2| \le 1. Each cell that is not on the border of the grid has eight immediate neighbours.

There are three integer parameters (a, b, c) which affect the game. The rules of the game are:

  • If a live cell has fewer than a live neighbours in the current generation it dies of loneliness. That is, it is dead in the next generation.
  • If a live cell has more than b live neighbours in the current generation it dies of overcrowding. That is, it is dead in the next generation.
  • If a dead cell has more than c live neighbours in the current generation it is born. That is, it is live in the next generation.
  • Otherwise, a cell's status is unchanged from the current generation to the next.

This process continues indefinitely. Eventually, a generation may be repeated in which case life goes on forever. Or all the cells may die. Similarly, if we explore previous generations that may have led to the current one, we may find one that is necessarily a first generation; that is, it could not have been created from a previous generation by following the rules. Such a generation is known as a Garden of Eden.

Given the game parameters and the current generation, you are to determine whether or not the game might have started with a Garden of Eden. If so, output the number of steps necessary to reach the current generation from the Garden of Eden. If there are several possible answers, find the smallest. If there is none, output -1.

Input Specification

There are m+1 lines of input in total.

The first line of input contains the game parameters, which are five integers m, n, a, b, c each separated by one space. The constraints are 1 \le m \le 4, 1 \le n \le 5, 1 \le a < b \le 8, 1 \le c \le 8.

The next m lines each contain a string of n characters representing a row of the current generation. In the string, an asterisk (*) indicates live while a period (.) indicates dead.

Sample Input

4 5 2 3 2
.****
.****
.****
.****

Sample Output

2

Explanation

Assume the sample input is the "current" generation. A possible previous generation is

**.**
..*.*
....*
*****

The above generation can be derived from the following previous generation

.****
**.*.
*****
*..*.

This generation cannot be derived from any other generation. Furthermore, there is no shorter series of generations that has these properties.

Comments


  • 0
    踏雪寻梅  commented on Sept. 28, 2024, 3:33 a.m.

    This question made me break out in a sweat🥵


  • -2
    can definitely solve contest problems in 4 seconds  commented on Oct. 23, 2023, 9:01 p.m.

    how did i possibly make it in pypy the first try while everyone else TLEs


  • 4
    melanie  commented on Jan. 27, 2021, 1:45 a.m.

    For people who are getting WA, if you're using boolean arrays (c++), for this problem try changing them to vectors (apparently large enough boolean arrays can cause problems). Thought I'd just put it here because I spent a lot of time debugging only to realize it was that simple. Hope it helps.


  • 5
    moladan123  commented on June 27, 2015, 9:58 p.m.

    Can anyone explain to me how pypy uses more than three times as much memory as vanilla python?


    • 13
      omaewamoushindeiru  commented on June 28, 2015, 12:40 a.m.

      Compared to cpython, pypy uses different garbage collection strategies. If the increase in memory is due to something in your program, you could try to run a forced garbage collection every now and then, by using the collect function from the gc module. In this case, it might also help to explicitly del large objects that you don't need anymore and that don't go out of scope.