Spreading
Leçon 31 sur 32 du cours Problèmes de programmation de Coddy.
Défi
DifficileDans un quartier, chaque voisin copie la couleur des maisons peintes en gris. Ainsi, le jour où certaines maisons sont peintes en gris, chaque voisin adjacent à ces maisons horizontalement et verticalement décide de peindre sa maison de la même manière. Ils ont besoin d'un mois pour cela. Après cela, les maisons adjacentes à celles-ci horizontalement et verticalement décident de faire la même chose, et elles prennent également un mois, et ainsi de suite.
####X ##XXX #XXXX XXXXX
##X## #XXXX XXXXX XXXXX
##### ##X## #XXXX XXXXX
Mo.1 Mo.2 Mo.3 Mo.4
Comme vous pouvez le voir, au début, seules deux maisons sont peintes en gris ([1,5] et [2,3]). Après un mois, 8 maisons sont peintes en gris, celles situées au-dessus, au-dessous, à droite et à gauche des maisons déjà peintes. Après deux mois, 13 maisons sont peintes en gris et après 3 mois, chaque maison du quartier est peinte en gris.
On vous donne deux nombres entiers naturels H et W en entrée, représentant la hauteur et la largeur du quartier. À la ligne suivante, on vous donne un nombre entier naturel N représentant le nombre de maisons qui doivent être peintes en gris. À la ligne suivante, on vous donne un nombre entier naturel M, et dans les M lignes suivantes, on vous donne deux nombres entiers naturels X et Y représentant les positions des maisons déjà peintes en gris.
Affichez combien de mois sont nécessaires pour qu'un total de N maisons soient peintes en gris (en incluant les maisons initialement peintes en gris).
Input
3 5
7
2
1 5
2 3
Output
1
Explanation #1: Nous avons l'exemple donné dans le texte ci-dessus. Ainsi, le quartier a une hauteur de 3 et une largeur de 5. Nous devons afficher combien de mois sont nécessaires pour qu'un total de 7 maisons soient peintes en gris. Il y a 2 maisons déjà peintes en gris, elles sont aux positions [1, 5] et [2,3]. Ainsi, un mois est nécessaire pour qu'un total de 7 maisons soient peintes en gris.
Essayez vous-même
#include <stdio.h>
int main() {
// Écrire le code ici
return 0;
}
Toutes les leçons de Problèmes de programmation
1Course Introduction
Introduction