Baktériumok
Néhány baktérium egy végtelen négyzetrács celláiban él, minden baktérium
a saját cellájában.
A következő transzformáció minden másodpercben lezajlik (minden cellára párhuzamosan):
- Ha egy baktériumnak sem felső, sem bal szomszédja nincs, akkor kihal.
- Ha egy cella üres, de tőle balra és felette is van baktérium, akkor ebben a cellában is születik egy baktérium.
A rács tanulmányozása során felfedezhető, hogy véges sok, téglalap alakú tartományban élnek baktériumok.
Határozzuk meg, hány másodperc alatt hal ki az összes baktérium.
Például:
Kezdetben 6 cellában él baktérium, és 6 másodperc alatt hal ki az összes. Az 1 olyan cellát jelöl, ahol van baktérium, a 0 olyat, ahol nincs.
000010 011100 010000 010000 000000 000000 001110 011000 010000 000000 000000 000110 001100 011000 000000 000000 000010 000110 001100 000000 000000 000000 000010 000110 000000 000000 000000 000000 000010 000000 000000 000000 000000 000000 000000
Bemenet
- Az első sorban a tesztesetek C száma van.
- Egy sorban R, a téglalap alakú tartományok száma, ahol baktériumok vannak.
- Ezután R sorban négy-négy szám, a téglalapok csúcsainak X1 Y1 X2 Y2 koordinátái. Ez azt jelenti, hogy minden cellában él baktérium, ahol a cella X koordinátája X1 és X2 közé, Y koordinátája pedig Y1 és Y2 közé esik, a határokat is megengedve.
Az Y tengely lefele mutat.
Kimenet
Minden tesztesetre ki kell írni a baktériumok kipusztulásának idejét, másodpercben.
Példa
| Bemenet | Kimenet |
1 |
Case #1: 6
|
Tesztadatok
Méretek
1 ≤ C ≤ 100.
Kicsi
1 ≤ R ≤ 10
1 ≤ X1 ≤ X2 ≤ 100
1 ≤ Y1 ≤ Y2 ≤ 100
1 ≤ X1 ≤ X2 ≤ 100
1 ≤ Y1 ≤ Y2 ≤ 100
Nagy
1 ≤ R ≤ 1000
1 ≤ X1 ≤ X2 ≤ 1000000
1 ≤ Y1 ≤ Y2 ≤ 1000000
Kezdetben legfeljebb 1000000 cellában él baktérium.
1 ≤ X1 ≤ X2 ≤ 1000000
1 ≤ Y1 ≤ Y2 ≤ 1000000
Kezdetben legfeljebb 1000000 cellában él baktérium.