Problema 2
Colonia de Bacterias
bacteria.pas, bacteria.c, bacteria.cpp

Problema
Un laboratorio de investigación distribuye una colonia de bacterias en un cultivo, que se puede considerar como una superficie cuadriculada de n filas y n columnas; cada casilla de esta superficie puede estar vacía o puede contener una bacteria. A partir de cualquier configuración inicial, la colonia evoluciona generación a generación según unas leyes genéticas fijas y determinadas y que dependen del número de vecinos que tenga cada casilla.
Para todas y cada una de las generaciones las leyes genéticas son:

Nacimiento: en toda casilla vacía que tenga exactamente tres vecinos.
Muerte por aislamiento: toda bacteria que ocupe una casilla con uno o ningún vecino.
Muerte por asfixia: toda bacteria que ocupe una casilla con más de tres vecinos.
Supervivencia: toda bacteria que ocupe una casilla con dos o tres vecinos.

La casilla que ocupa la fila i y la columna j se identifica mediante (i, j) (1 ≤ i ≤ n, 1 ≤ j ≤ n). Los vecinos de una casilla (i, j) son las posiciones (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j) e (i+1, j+1) que estén comprendidas dentro de la superficie y que estén ocupadas por una bacteria. Así, en una superficie 4×4, la colonia de la izquierda de la figura siguiente evoluciona en las dos próximas generaciones tal y como se muestra:

Se pide simular la evolución de una colonia inicial durante un cierto número de transiciones.

Entrada
Línea 1: valor de n (uno o dos caracteres que representen un número entero entre 1 y 20).
Línea 2: número de transiciones a estudiar (varios caracteres que representen un número entero no negativo)
Líneas siguientes: cada línea contiene una pareja de uno o dos caracteres, para representar la posición que ocupa una bacteria en la configuración inicial de la colonia, empezando por la columna y después el renglón. Los dos elementos de la pareja estarán separados por un único blanco. Cada elemento de la pareja representa pues un número comprendido entre 1 y n.

Salida
La colonia resultante de aplicar las reglas descritas en el enunciado. Representamos la colonia con n líneas de n caracteres. Cada carácter de esta superficie n×n será o bien un carácter 'o' o bien un carácter 'x', según la casilla correspondiente esté vacía o bien ocupada por una bacteria, respectivamente.

Ejemplo