Informatika gyűjtemény

Egy szinttel feljebb Baktériumok

2004050607080910

NézetNyomtat

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):
  1. Ha egy baktériumnak sem felső, sem bal szomszédja nincs, akkor kihal.
  2. 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 ≤ X1X2 ≤ 100
1 ≤ Y1Y2 ≤ 100

Nagy

1 ≤ R ≤ 1000
1 ≤ X1X2 ≤ 1000000
1 ≤ Y1Y2 ≤ 1000000

Kezdetben legfeljebb 1000000 cellában él baktérium.