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
