Wirusy
Limit pamięci: 32 MB
Mamy daną tablicę o rozmiarach ,
których komórki indeksujemy parami liczb całkowitych ,
.
Z początku komórki są puste, ale z czasem pojawiają się na niej wirusy różnych rodzajów
i zaczynają się rozmnażać.
Każdy wirus ma określony czas pojawienia jako dzień i godzinę,
oraz miejsce pojawienia jako współrzędne komórki.
Następnie wirus każdego dnia o zadanej godzinie
(tej samej, w której się po raz pierwszy pojawił) aktywuje się i replikuje się.
Replikacja polega na zajęciu wszystkich wolnych komórek,
które sąsiadują z wirusem danego rodzaju.
Komórki i są sąsiadujące, jeżeli .
Wirusy replikują się tak długo, aż zajmą całą tablicę.
Wirus może się w ogóle nie pojawić w przypadku, gdy miejsce pojawienia się jest już zajęte przez innego wirusa.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis wirusów,
- dla każdego wirusa wyznaczy liczbę zajętych komórek,
- zapisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i
oddzielone pojedynczym odstępem, , .
Każdy z następnych wierszy zawiera cztery liczby całkowite , , i ,
, , pooddzielanych pojedynczymi odstępami, oznaczające
odpowiednio godzinę, dzień i współrzędne pojawienia się wirusa.
Można założyć, że nie istnieją dwa wirusy o tej samej godzinie pojawienia się,
tzn. wartość parametru nie powtórzy się na wejściu.
Wyjście
Wyjście powinno składać się z liczb całkowitych w osobnych wierszach
oznaczających liczbę zajętych komórek przez poszczególne wirusy.
Przykład
Do czytelniejszego przedstawienia przykładowego wejścia i wyjścia
zostały użyte kolorowe czcionki.
Dla danych wejściowych:
5 4
1 2 4 4
2 1 5 1
0 3 1 3
3 3 3 3
poprawną odpowiedzią jest:
10
7
8
0
5 |
4 |
3 |
3 |
3 |
4 |
4 |
3 |
2 |
3 |
3 |
4 |
3 |
3 |
3 |
4 |
4 |
3 |
2 |
2 |
5 |
4 |
3 |
2 |
1 |
Dla każdej komórki, kolor oznacza wirusa, który ją zajął,
a liczba oznacza dzień, w którym została zajęta dana komórka.
Komórka o współrzędnych jest w lewym dolnym rogu.
Autor zadania: Jakub Pawlewicz.