Spreading
Lektion 31 von 32 im Kurs Programmieraufgaben von Coddy.
Aufgabe
SchwerIn einer Nachbarschaft kopiert jeder Nachbar die Farbe der grau gestrichenen Häuser. An dem Tag, an dem einige Häuser grau gestrichen werden, beschließt jeder Nachbar, der horizontal oder vertikal an diese Häuser angrenzt, sein Haus auf die gleiche Weise zu streichen. Dafür benötigen sie einen Monat. Danach beschließen die Häuser, die horizontal und vertikal an diese angrenzen, dasselbe zu tun, was ebenfalls einen Monat dauert, und so weiter.
####X ##XXX #XXXX XXXXX
##X## #XXXX XXXXX XXXXX
##### ##X## #XXXX XXXXX
Mo.1 Mo.2 Mo.3 Mo.4
Wie Sie sehen können, sind am Anfang nur zwei Häuser grau gestrichen ([1,5] und [2,3]). Nach einem Monat sind 8 Häuser grau gestrichen, nämlich die oberhalb, unterhalb, rechts und links von den bereits gestrichenen Häusern. Nach zwei Monaten sind 13 Häuser grau gestrichen und nach 3 Monaten ist jedes Haus in der Nachbarschaft grau gestrichen.
Sie erhalten zwei natürliche Zahlen H und W als Eingabe, die die Höhe und Breite der Nachbarschaft darstellen. In der nächsten Zeile erhalten Sie eine natürliche Zahl N, die die Anzahl der Häuser darstellt, die grau gestrichen werden müssen. In der nächsten Zeile erhalten Sie eine natürliche Zahl M, und in den nächsten M Zeilen erhalten Sie zwei natürliche Zahlen X und Y, die die Positionen der bereits grau gestrichenen Häuser darstellen.
Geben Sie aus, wie viele Monate benötigt werden, damit insgesamt N Häuser grau gestrichen sind (einschließlich der Häuser, die anfangs grau gestrichen waren).
Input
3 5
7
2
1 5
2 3
Output
1
Erklärung #1: Wir haben das Beispiel aus dem obigen Text. Die Nachbarschaft hat also eine Höhe von 3 und eine Breite von 5. Wir müssen ausgeben, wie viele Monate benötigt werden, damit insgesamt 7 Häuser grau gestrichen sind. Es sind bereits 2 Häuser grau gestrichen, sie befinden sich an den Positionen [1, 5] und [2,3]. Somit wird ein Monat benötigt, damit insgesamt 7 Häuser grau gestrichen sind.
Probier es selbst
#include <stdio.h>
int main() {
// Code hier schreiben
return 0;
}
Alle Lektionen in Programmieraufgaben
1Course Introduction
Introduction