Nivel 3 Problema 2 laboratorio Certamen Nacional OIA 2019

Laboratorio lleno de perrosContribución de Lautaro Lasorsa

Descripción del problema

En un congreso reciente, se usó ellaboratorio de informática para realizaractividades. Había muchos perros mero-deando. Los perros fueron entrando allaboratorio y obstruyendo el paso.

Más específicamente, el laboratoriopuede representarse como una grilla deNxM baldosas. Cada baldosa puede:

Estar libre, de modo que se puedetransitar sobre ella.

Tener un escritorio encima, de modoque no se puede transitar por allí.

El laboratorio tiene una única entrada,que puede abarcar varias baldosas ale-dañas a la entrada. Una baldosa libre esaccesible si existe un camino que pasaexclusivamente por baldosas libres y queune la entrada con dicha baldosa. Esposible moverse desde una baldosa haciaotra cuando ambas comparten un lado.

Los escritorios están ubicados de formatal que cuando no hay perros, todas lasbaldosas libres son accesibles. Se sabeque han ingresado P perros, todos enmomentos distintos:

Cuando un perro entra, se recues-ta sobre una baldosa libre, blo-queándola de modo que ya no sepuede transitar por allí. Como estámuy cómodo allí, permanecerá inde-finidamente en ese lugar.

Los perros son ágiles y además sepermiten el paso mutualmente, porlo que un perro podrá recostarse enuna baldosa libre incluso si esta noes accesible para las personas.

Debes escribir una función que dado elmapa del laboratorio y los ingresos perru-nos, calcule cuántas baldosas accesibleshabía luego de entrar cada perro.

Detalles de implementación

Se debe implementar la funcionlaboratorio(mapa, perrosF, perrosC).Sus parámetros son:

mapa es un arreglo de N cadenasde caracteres de longitud M, tal queel caracter en la posición mapa[i][j]describe la baldosa en fila i y colum-na j (0 ≤ i ≤ N − 1, 0 ≤ j ≤ M − 1).Su valor será :

• . si es una baldosa libre.

• # si hay un escritorio.

• E si es una baldosa aledaña ala entrada. Todas las baldosas Eestán en el borde del laboratorio,y son vecinas entre sí. Las bal-dosas E son, a su vez, baldosaslibres.

perrosF, perrosC son arreglos de Penteros, de modo que perrosF[i] yperrosC[i] indican respectivamentela fila y columna en la cual se ubicaráel i-ésimo perro en orden de ingreso(0 ≤ i ≤ P − 1).

La función debe retornar un arreglo deP enteros, que contenga las cantidadesde baldosas libres accesibles luego deque ingresara cada perro, en orden deingreso.

hoja 1 de 3

Nivel 3 Problema 2 laboratorio Certamen Nacional OIA 2019

Evaluador local

El evaluador local lee de la entradaestándar:

Una línea con los enteros N, M y P

N líneas de M caracteres cada una,sin espacios, que describen el mapadel laboratorio.

Luego P líneas, cada una con dosenteros. La i-ésima de estas líneas(contando desde 0) contiene los en-teros perrosF[i] y perrosC[i].

Escribe a la salida estándar una lí-nea el arreglo retornado por la funciónlaboratorio.

Cotas

1 ≤ N × M ≤ 200.000

1 ≤ P ≤ 100.000

0 ≤ perrosF [i ] ≤ N − 1

0 ≤ perrosC[i ] ≤ M − 1

Ejemplos

Si el evaluador local recibe la siguienteentrada:

4 4 5...##...E..#E..#1 30 00 12 03 0

Una implementación correcta deberádevolver:

11 10 9 8 0

Si en cambio recibe:

1 10 5#....E...#0 20 10 50 60 7

Se debe devolver:

6 6 0 0 0

Y si en cambio se recibe :

10 10 6E..#...#..E..#...#..E..#...#..E..##.##.#E.........E..##.##.#E..#...#..E..#...#..E..#...#..E..#...#..3 55 53 85 84 74 3

Se debe devolver:

66 53 46 37 34 30

hoja 2 de 3

Nivel 3 Problema 2 laboratorio Certamen Nacional OIA 2019

A continuación se muestra la situaciónluego de ingresado el primer perro:

Luego de ingresar el tercer perro que-daría:

Y la situación final es:

Subtareas

1. N = 1, y hay exactamente una bal-dosa aledaña a la entrada (8 puntos)

2. N = 1 (12 puntos)

3. P = 1 (15 puntos)

4. N × M × P ≤ 100.000 (25 puntos)

5. Sin más restricciones (40 puntos)

hoja 3 de 3