Pilietinis civilizuotų ląstelių karas


Pradinių duomenų failas:
lasteles.in  
Rezultatų failas:
lasteles.out  
Laiko apribojimas:
7 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Kažkur, žmogaus organizme, netoli nuo čia, vyksta keistas karas tarp dviejų tipų ląstelių: A-ląstelių ir Z-ląstelių. Abi jos siekia išnaikinti priešingo tipo ląsteles vardan valdžios, pinigų bei geresnių gyvenimo sąlygų.

Mūsų modelyje mūšis tarp A-ląstelių ir Z-ląstelių vyksta dvimatėje lentelėje, kurios kiekvienas langelis gali būti užimtas A-ląstelės, Z-ląstelės arba būti tuščias. Būdamos gana švelnios, ląstelės kariauja ėjimais: kiekvienu ėjimu viena ląstelė (A arba Z tipo, priklausomai, kieno ėjimas) privalo užpulti ir sunaikinti kitos rūšies ląstelę, esančią gretimame langelyje (aukščiau, žemiau, kairėj arba dešinėj). Ši ląstelė taip pat ir persikelia į gretimą langelį, kuriame buvo auka. Jei kurios nors ląstelės išnaikina visas kito tipo ląsteles, jos, be abejo, laimi mūšį. Jei ėjimu neįmanoma jokia ataka, tai šios rūšies ląstelės sunyksta iš gėdos, ir laimi kita ląstelių rūšis. Mūšį visuomet pradeda A-ląstelės.

Žemiau pavaizduotas mūšio laukas, bei A-ląstelių atliekamas ėjimas. Ėjimas nėra labai protingas, kadangi sekančiu ėjimu Z-ląstelė gali atakuoti A-ląstelę langelyje (3, 3) ir laimėti mūšį. Jei A-ląstelės pirmu ėjimu būtų atakavusios Z-ląstelę langelyje (3, 1), mūšį būtų laimėjusios jos.

Vis dažniau į neviltį puolančios Z-ląstelės nusprendė, kad joms reikia Smegenų pagalbos, ir kreipėsi į šias, prašydamos padėti laimėti mūšį. A-ląstelės, savo ruožtu, kreipėsi į Burną, kuri pas daugelį žmonių veikia nepriklausomai nuo smegenų. Vadovaujamos šių galių, A-ląstelės ir Z-ląstelės dabar kariauja optimaliai. Kitaip tariant, jei kurios nors rūšies ląstelėms egzistuoja galimybė atlikti ėjimus taip, kad jos laimėtų, nesvarbu, ką darytų priešininkės ląstelės, tai šios rūšies ląstelės taip ir kariaus.

Jūsų užduotis – padėti mums nustatyti, kurios ląstelės laimės mūšį, kai žinomas pradinis ląstelių išsidėstymas mūšio lauke.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas lauko ilgis I ir plotis P. Nei I, nei P neviršys 20. Sekančiose P eilučių pateikiamas pats mūšio laukas, užpildytas simboliais ‘A’, ‘Z’ ir ‘.’, žyminčiais, kad langelis užimtas A-ląstelės, Z-ląstelės arba yra tuščias, atitinkamai. Bendras ląstelių skaičius mūšio lauke neviršys 25.

Rezultatai

Į rezultatų failą programa turi išvesti raidę A arba Z, žyminčią, kas laimės šį mūšį.

Pavyzdžiai

Pradiniai duomenys Rezultatai
3 3
Z.A
AA.
Z.Z
A
3 3
AZA
.AZ
AZA
A
3 3
ZZZ
ZAA
ZAA
Z
5 2
ZZAZA
AZ.AA
A