Úloha: Grafický editor

Jednoduchý grafický bitmapový editor má k dispozici čtyři příkazy.
Příkaz R nakreslí plný obdélník.
Příkaz H nakreslí nevyplněný obdélník.
Příkaz F vyplní danou barvou souvislou oblast.
Příkaz E ukončí posloupnost příkazů.

Identifikátory příkazů mnemonicky reflektují anglickou variantu příkazů: R = Rectangle, H = Hollow rectangle, F = Flood Fill, E = End.
Editor pracuje na obrázku o rozměru H x W, kde H je výška (Height) obrázku v pixelech a W je šířka (Width) obrázku v pixelech. Souřadnice y roste z levého horního rohu směrem dolů, souřadnice x roste z levého horního rohu směrem doprava. Při identifikaci pixelu se uvádí nejprve jeho y souřadnice a pak x souřadnice. Pixel v levém horním rohu obrázku má souřadnice [0,0], pixel v pravém dolním rohu obrázku má souřadnice [H-1, W-1]. Každý pixel může být vybarven jednou z 256 barev, každá barva je identifikována svým číslem 0 - 255.

Příkaz R má syntax
R<mezera><y1><mezera><x1><mezera><y2><mezera><x2><mezera><c>
Všechny parametry jsou celá čísla, hodnota parametru <c> je vždy v rozmezí 0-255, hodnoty ostatních parametrů mohou být libovolné. Dvojice hodnot <y1> <x1> představuje souřadnice pixelu p1, dvojice hodnot <y2> <x2> představuje souřadnice pixelu p2. Pixely p1 a p2 představují protější rohy obdélníku, který má být celý vybarven barvou <c> bez ohledu na to, jak jsou předtím vybarveny jednotlivé pixely ležící v tomto obdélníku. Všechny parametry jsou celá čísla, hodnota parametru <<c> je vždy v rozmezí 0-255,hodnoty ostatních parametrů mohou být libovolné.

Příkaz H má syntax
H<mezera><y1><mezera><x1><mezera><y2><mezera><x2><mezera><th><mezera><c>
Všechny parametry jsou celá čísla, hodnota parametru <c> je vždy v rozmezí 0-255, hodnoty ostatních parametrů mohou být libovolné. Dvojice hodnot <y1> <x1> představuje souřadnice pixelu p1, dvojice hodnot <y2> <x2> představuje souřadnice pixelu p2. Pixely p1 a p2 představují protější rohy obdélníku. Příkaz nakreslí pouze hranici obdélníku o tloušťce <th> pixelů. Tloušťka kreslené čáry se počítá směrem dovnitř od okraje obdélníku. Pokud je tloušťka čáry natolik veliká, že je celý vnitřek obdélníka vybarven, je efekt příkazu H <y1> <x1> <y2> <x2> <th> <c> stejný jako efekt příkazu R <y1> <x1> <y2> <x2> <c>. Pokud je tlouštka čáry nulová nebo záporná, příkaz nemá žádný efekt na obrázek.

Souřadnice v příkazech R a H
Pokud leží některá ze souřadnic příkazu mimo prostor obrázku, použije příkaz následující strategii: Představme si, že je k dispozici virtuální neomezená rovina pixelů, z níž se zobrazuje pouze část daná polohou a velikostí obrázku. Příkaz nakreslí celý obdélník do této roviny, a v obrázku se pak zobrazí pouze jeho příslušná část, tj. průnik obdélníku ve virtuální rovině s daným obrázkem. Efekt příkazu se proto může lišit podle velikosti obrázku. Například příkaz H -10 -100 2 200 1 99 vybarví barvou 99 všechny pixely ve třetí řadě shora v obrázku o šířce 100. V obrázku o šířce 1000 nakreslí "skobu" v jeho levém horním rohu, to jest vyplní barvou 99 pixely o souřadnicích [2, x] pro x = 0..200 a navíc pixely se souřadnicemi [0, 200] a [1, 200].

Příkaz F má syntax
F<y1><mezera><x1><mezera><c>
Příkaz vyplní barvou <c> maximální souvislou oblast, která obsahuje pixel o souřadnicích [<y1>, <x1>] a jejíž všechny pixely mají stejnou barvu jako tento pixel. Souvislá oblast pixelů je definována tak, že v ní lze přejít z libovolného jednoho pixelu do jiného pixelu tím způsobem, že se opakovaně přesunujeme z jednoho pixelu do sousedního pouze směrem nahoru, dolů, doprava nebo doleva, nikdy úhlopříčně nebo skokem, a přitom nikdy neopustíme tuto oblast. Pokud pixel o souřadnicích [<y1>, <x1>] leží mimo obrázek, příkaz nemá žádný efekt na obrázek.

Příkaz E nemá žádné parametry a jeho zápisem je jediný znak E.

Před zahájením práce jsou všechny pixely obrázku inicializovány barvou 0.

Vstup

Na vstupu je nejprve jeden řádek se dvěma celými kladnými čísly H a W, oddělenými mezerou, které představují výšku a šířku obrázku. Následuje seznam příkazů, každý příkaz seznamu je napsán na jednom řádku, řádek neobsahuje úvodní mezery a všechny údaje na řádku jsou odděleny jedinou mezerou. Posledním příkazem v seznamu je příkaz E. Počet příkazů na vstupu je nejvýše 1 000 000.

Výstup

Na výstupu je seznam všech barev, které byly použity, včetně barvy 0. Seznam je uspořádán podle hodnot barev v rostoucím pořadí. Každá položka seznamu je zapsána na jednom řádku a obsahuje dvě čísla. První číslo je hodnota barvy a druhé představuje počet pixelů v obrázku obarvených touto barvou po provedení všech příkazů.

Příklad

Vstup:

11 10 
H 3 3 8 7 2 99
H 7 1 400 9 1 99
R 5 7 7 8 11
F 4 7 55
E

Výstup:

0 70
11 6
55 30
99 4

Barvy jednotlivých pixelů po provedení uvedených příkazů jsou schematicky znázorněny níže.

   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0  55  55  55  55  55   0   0
   0   0   0  55  55  55  55  55   0   0
   0   0   0  55  55   0  55  11  11   0
   0   0   0  55  55   0  55  11  11   0
   0  55  55  55  55  55  55  11  11  99
   0  55   0  55  55  55  55  55   0  99
   0  55   0   0   0   0   0   0   0  99
   0  55   0   0   0   0   0   0   0  99

Testovací data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data