Spreading
Lección 31 de 32 del curso Problemas de programación de Coddy.
Desafío
DifícilEn un vecindario, cada vecino copia el color de las casas pintadas de gris. Así, el día en que algunas casas se pintan de gris, cada vecino junto a esas casas, horizontal y verticalmente, decide pintar su casa de la misma manera. Necesitan un mes para eso. Después de eso, las casas junto a ellas, horizontal y verticalmente, deciden hacer lo mismo, y también les toma un mes, y así sucesivamente.
####X ##XXX #XXXX XXXXX
##X## #XXXX XXXXX XXXXX
##### ##X## #XXXX XXXXX
Mo.1 Mo.2 Mo.3 Mo.4
Como puedes ver, al principio solo dos casas están pintadas de gris ([1,5] y [2,3]). Después de un mes, 8 casas están pintadas de gris, las que están arriba, abajo, a la derecha y a la izquierda de las casas ya pintadas. Después de dos meses, 13 casas están pintadas de gris y después de 3 meses todas las casas del vecindario están pintadas de gris.
Se te dan dos números naturales H y W de la entrada, que representan la altura y el ancho del vecindario. En la siguiente línea se te da un número natural N que representa el número de casas que deben estar pintadas de gris. En la siguiente línea se te da un número natural M, y en las siguientes M líneas se te dan dos números naturales X e Y que representan las posiciones de las casas que ya están pintadas de gris.
Imprime cuántos meses se necesitan para que un total de N casas estén pintadas de gris (incluyendo las casas que están pintadas de gris inicialmente).
Input
3 5
7
2
1 5
2 3
Output
1
Explicación #1: Tenemos el ejemplo dado en el texto anterior. Así, el vecindario tiene una altura de 3 y un ancho de 5. Necesitamos imprimir cuántos meses se necesitan para que un total de 7 casas estén pintadas de gris. Hay 2 casas ya pintadas de gris en las posiciones [1, 5] y [2,3]. Por lo tanto, se necesita un mes para que un total de 7 casas estén pintadas de gris.
Pruébalo tú mismo
#include <stdio.h>
int main() {
// Escribe el código aquí
return 0;
}
Todas las lecciones de Problemas de programación
1Course Introduction
Introduction