Nome do arquivo: jogo.x, onde x deve ser c, cpp, java, js ou py
Fonte: OBI2024

O Jogo da Vida de Conway é um processo de simulação (conhecido como autômato celular) criado pelo matemático britânico John Conway para reproduzir, por meio de uma matriz, processos de mudança em grupos de seres vivos. As regras do jogo indicam como a matriz é modificada a cada passo. Os valores da matriz em um determinado passo são coletivamente chamados de estado do jogo.

Mais especificamente, o jogo acontece em uma matriz quadrada N x N (ou seja, com N linhas e N colunas) no qual cada célula está viva (representada pelo número 1) ou morta (representada pelo número 0). Para simular o próximo estado do autômato, para cada célula calculamos o seu número de vizinhos vivos (duas células são consideradas vizinhas se elas são adjacentes diagonalmente, horizontalmente ou verticalmente - ou seja, uma célula pode ter até 8 vizinhas), e decidimos se a célula estará viva ou morta no próximo estado de acordo com as seguintes cinco regras:

1. se uma célula morta possui exatamente 3 vizinhas vivas, ela vira uma célula viva;
2. se uma célula morta possui uma quantidade de vizinhas diferente de 3, ela continua morta;
3. se uma célula viva possui 2 ou 3 vizinhas vivas, ela continua viva;
4. se uma célula viva possui menos que 2 vizinhas vivas, ela morre;
5. se uma célula viva possui mais que 3 vizinhas vivas, ela morre;

Toda célula fora da matriz é considerada morta, ou seja, células fora da matriz nunca afetam a quantidade de vizinhos vivos de alguma célula. Observe que as regras são aplicadas em todas as células simultaneamente, uma vez a cada passo.

Dada uma matriz que representa o estado inicial do jogo e um inteiro positivo Q, sua tarefa é determinar o Q-ésimo estado do jogo de acordo com as regras descritas acima, ou seja, o valor de cada célula da matriz após Q passos do jogo.

A figura abaixo mostra um exemplo de jogo em uma matriz 5 x 5 e seus estados para diferentes valores de Q. Células vivas são representadas com a cor preta e células mortas são representadas com a cor branca.