Ősi üzenetek

A korai civilizációk megértése érdekében az archeológusok gyakran tanulmányoznak ősi nyelveken íródott szövegeket. Az egyik ilyen nyelv, amelyet Egyiptomban használtak több mint 3000 évvel ezelőtt, hieroglifáknak nevezett karaktereken alapul. Az 1. ábra hat hieroglifát mutat be a nevükkel együtt. Ebben a feladatban egy olyan programot kell írnod, amely képes felismerni ezt a hat karaktert.

1. ábra: Hat hieroglifa

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. A tesztesetek mindegyike egy olyan képet ír le, amelyen az 1. ábrán látható hieroglifák közül szerepel egy vagy több. A kép (1-essel reprezentált) fekete és (0-val reprezentált) fehér pixelekből álló vízszintes sorok sorozataként lesz megadva. A bemeneten minden sor hexadecimális jelöléssel lesz kódolva. A nyolc pixelből álló 10011100 sorozat (egy fekete pixel, majd két fehér pixel stb.) például hexadecimális jelöléssel 9c lesz. A hexadecimális kódban csak számjegyek és kisbetűk szerepelnek a-tól f-ig. Minden teszteset első sora két egész számot tartalmaz: H-t és W-t. H (0 < H ≤ 200) a kép sorainak a száma, míg W (0 < W ≤ 50) az egyes sorokban szereplő hexadecimális karakterek száma. A következő H sor a kép hexadecimális karaktereit adja meg felülről lefelé haladva. A bemeneten megadott képek megfelelnek a következő szabályoknak:

A kép csak az 1. ábrán látható hieroglifákat tartalmaz.
Minden képen szerepel legalább egy szabályos hieroglifa.
A kép mindegyik fekete pixele egy szabályos hieroglifa része.
Minden hieroglifát fekete pixelek összefüggő sorozata ad meg, és minden fekete pixel felső, alsó, bal vagy jobb oldalán legalább egy másik fekete pixel van.
A hieroglifák nem érintik egymást, és egyik hieroglifa sincs egy másik belsejében.
Két, egymást átlósan érintő fekete pixelhez mindig tartozik egy közösen érintett fekete pixel.
A hieroglifák lehetnek ugyan torzítottak, de mindegyiknek olyan alakja van, amely topologikusan ekvivalens az 1. ábrán látható valamelyik szimbólummal. (Két alakzat topologikusan ekvivalens, ha átvihetők egymásba nyújtással, de vágás nélkül.)

Az utolsó tesztesetet egy olyan sor követi, amely két nullát tartalmaz.

A kimenet specifikációja

Minden tesztesetre a teszteset sorszámát követően egy olyan sztringet kell a kimenetre írni, amely a képen felismert minden hieroglifához egyetlen karaktert tartalmaz az alábbi kódolás szerint:

Ankh: A
Wedjat: J
Djed: D
Scarab: S
Was: W
Akhet: K

A kimeneti sztringekben a kódokat alfabetikus sorrendben kell megadni. Kövesd a példa kimenet formátumát!

A példa bemenet a 2. és 3. ábrán látható tesztesetek leírásait tartalmazza. Hely hiányában nem adjuk meg a példa bemenet összes sorát.

2. és 3. ábra: A példa bemenet tesztesetei

Példa bemenet

100 25
0000000000000000000000000
0000000000000000000000000
...(50 lines omitted)...
00001fe0000000000007c0000
00003fe0000000000007c0000
...(44 lines omitted)...
0000000000000000000000000
0000000000000000000000000
150 38
00000000000000000000000000000000000000
00000000000000000000000000000000000000
...(75 lines omitted)...
0000000003fffffffffffffffff00000000000
0000000003fffffffffffffffff00000000000
...(69 lines omitted)...
00000000000000000000000000000000000000
00000000000000000000000000000000000000
0 0

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

Case 1: AKW
Case 2: AAAAA