[ED088] Jogo da Vida

Para efeitos da nota atribuida à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 29 de Outubro
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #04]

[ED088] Jogo da Vida

O problema

O Jogo da Vida (Game of Life ou Life) é um autómato celular proposto em 1970 pelo matemático britânico John Horton Connway. Na realidade, trata-se de uma simulação e não de um jogo com jogadores. Desenvolve-se numa grelha infinita, na qual cada célula pode estar ocupada por um organismo ou não. Células ocupadas dizem-se que estão vivas e as não ocupadas dizem-se mortas. Em cada geração as células que estão vivas mudam o seu estado em função do número de células vizinhas que estão vivas de acordo com as seguintes regras:

Os vizinhos de uma célula são as 8 células que a tocam na horizontal, vertical ou diagonal.
Se uma célula estiver viva e o número de células vizinhas vivas for 0 ou 1, então na geração seguinte a célula morre de solidão.
Se uma célula está viva e tem 4 ou mais células vizinhas também vivas, então na geração seguinte a célula morre de sobre-povoamento.
Uma célula viva com 2 ou 3 células vizinhas vivas, continua viva na geração seguinte.
Se uma célula morta tiver exactamente 3 células vizinhas vivas, muda para o estado de célula viva na geração seguinte.
Todos os nascimentos e mortes de células têm lugar em simultâneo, isto é as alterações têm por base o estado actual e nunca o estado futuro.

As figuras seguintes ilustram dois estados consecutivos de uma configuração do jogo da vida.

Neste problema vamos considerar que a grelha é finita e que as células que a envolvem estão sempre mortas.

Input

A primeira linha contém três inteiros positivos: o número de linhas L e de colunas C que determinam a dimensão da grelha do jogo e o número de iterações I que deverá realizar.

Seguem-se L linhas de caracteres a representar o estado actual do jogo. As células mortas estão representadas por '.' e as vivas por 'O'.

Output

Deve imprimir o estado do jogo ao fim de I iterações, isto é, imprimir a matriz que representa a grelha do jogo com as células mortas marcadas com '.' e as células vivas com 'O'.

Exemplo de input/output

Input	Output
5 5 5 ..... ..... .OOO. ..... .....	..... ..O.. ..O.. ..O.. .....

Estruturas de Dados (CC1007)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto