teddy online judge

910. Antivirus

Limite de tiempo : 1 seg.   Total runs : 66  Aceptados : 22

Si todas las personas en el planeta se mantuvieran alejados el uno del otro por un par de semanas, ¿no sería el resfriado común exterminado?

El resfriado común es causado por una gran variedad de virus. Siendo los rinovirus los más comunes, estos virus se apoderan de las células en la nariz y la garganta y las utilizan para la repdouccion de mas virus. Al cabo de unos días, tu sistema inmunológico detecta y destruye el virus, no sin antes haber infectado, en promedio, a otra persona. Después de luchar contra la infección, ahora eres inmune a ese rinovirus en particular, una inmunidad que dura años.

Si nos pusieran en cuarentena, los virus del resfriado que llevamos no tendrían anfitriones frescos para contagiar. ¿Podrían entonces nuestros sistemas inmunológicos, erradicar todas las copias del virus?

Dado un mapa de las posiciones de las personas en un mundo imaginario, determina si es posible eliminar el virus totalmente. En este mundo imaginario una persona con el Virus es denotada por una letra V y una persona que no esta enferma esta denotada por la letra P. Una persona infectada puede transmitir el virus a todas las personas que están rodeándola, izquierda, derecha, arriba, abajo y también en diagonales.

Entrada

Un numero c que indica la cantidad de casos de prueba a seguir. Cada caso consiste de una linea con un entero i, seguido de una linea con un entero f denotando a cuantas personas debe infectar un virus para que pueda sobrevivir la cuarentena, seguido de i lineas que describen un arreglo de i * i .

El arreglo bi dimensional puede incluir una de las siguientes caracteres:

• P representa una persona que puede ser contagiada.
• V representa una persona contagiada con el virus
• . representa un espacio vacio sin persona a quien contagiar

Salida

Virus eliminado si el virus solo puede infectar a menos de f personas. Contagiados de por vida si el virus puede extenderse a f o mas personas.

Entrada de ejemplo

2
5
8
..P..
...P.
P.P.P
VP...
....P
5
3
..P..
...P.
..P.P
VP...
....P

Salida de ejemplo

Virus eliminado
Contagiados de por vida