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.
Ezután minden tesztesetre :
- 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.
A téglalapok átfedhetik egymást.
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
3
5 1 5 1
2 2 4 2
2 3 2 4
|
Case #1: 6
|
Tesztadatok
Méretek
1 ≤ C ≤ 100.
Kicsi
1 ≤ R ≤ 10
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.
