L žaidimas ©Edward de Bono

L žaidimą sukūrė Edvardas de Bono, kuriam patinka žaisti stalo žaidimus ir kuris nemėgsta žaidimų su daug figūrų. Jis ketino sukurti kuo paprastesnį žaidimą, kuriam žaisti reiktų didelio meistriškumo. L žaidimas ir yra šių ketinimų rezultatas.

Abu žaidėjai turi po vieną L figūrą. Dar yra dvi neutralios (t.y. nepriklausančios nė vienam žaidėjui) šaškės. Lentos išmatavimai: 44. Žaidimo tikslas: įstumti priešininką į tokią poziciją, kad jis negalėtų pajudinti savo L figūros.

Duota kažkokia pradinė pozicija, kai abiejų žaidėjų L figūros ir abi šaškės išdėstytos lentoje. Žaidėjas, kurio eilė paeiti, pirmiausia paeina su L figūra. Ėjimas su L figūra reiškia, kad žaidėjas pakelia figūrą ir ją padeda bet kurioje kitoje laisvoje vietoje. Prieš dedant, figūrą galima apversti (t.y. pakeisti L orientaciją). Padėta figūra privalo užimti keturis langelius.

Paėjęs su L figūra, žaidėjas gali perkelti bet kurią vieną (tik vieną) šaškę į bet kurį laisvą lentos langelį. Atkreipkite dėmesį, kad paeiti su šaške nebūtina!

Paveikslėliuose pateiktos trys pradinės situacijos. Iš bet kurios pateiktos situacijos žaidėjas, kuriam priklauso languota L figūra, gali paeiti su L figūra į dvi skirtingas pozicijas (tos pozicijos parodytos dvejuose likusiuose paveikslėliuose). Paėjęs L figūra, žaidėjas gali paeiti bet kuria šaške į bet kurį iš likusių laisvų 6 langelių arba visai nejudinti šaškės. Viso yra 2(6+6+1) galimi ėjimai.

Žaidėjas laimi, jei priešininkas nebegali paeiti savo L figūra. Jeigu žemiau pateiktame pavyzdyje atėjo eilė paeiti žaidėjui su languota figūra, jis pralaimi, nes negali paeiti su L figūra.

Žaidimas paprastas ir kartu sudėtingas, nes yra labai daug ėjimų. Iš viso yra daugiau nei 18,000 variantų, kaip išdėstyti L figūras ir šaškes šioje mažoje lentoje, ir bet kuriuo žaidimo momentu gali būti iki 195 galimų skirtingų ėjimų, iš kurių tik vienas bus sėkmingas.

UŽDUOTIS
Duota tam tikra situacija lentoje, taip pat žinoma, kuris žaidėjas turi paeiti. Pavadinkime šį žaidėją pirmuoju, o likusį žaidėją – priešininku. Parašykite programą, kuri nuspręstų, ar tas žaidėjas turi laimintį ėjimą, ir, jei taip, jį surastų. Jei egzistuoja keli laimintys ėjimai, reikia išvesti bet kurį vieną. Jei laiminčio ėjimo nėra, programa turi nuspręsti, ar žaidimas baigsis lygiosiomis (laikant, kad abu žaidėjai žaidžia optimaliai), ar pirmasis žaidėjas pralaimės.

Ėjimas vadinamas laiminčiu, jei pirmajam žaidėjui atlikus šį ėjimą ir toliau optimaliai žaidžiant, jo priešininkas būtinai pralaimės, nepriklausomai nuo to, kaip priešininkas žais.

Pirmasis žaidėjas pralaimės, jeigu nesvarbu kaip jis žaistų, jo optimaliai žaidžiantis priešininkas laimės.

Jeigu nei viena iš dviejų aukščiau aprašytų sąlygų neišpildoma (t.y. nė vienas žaidėjas negali užsitikrinti, kad optimaliai abiems žaidžiant, laimės), laikoma, kad žaidimas baigsis lygiosiomis.

PRADINIAI DUOMENYS
Pradiniai duomenys įrašyti byloje lgame.in. Pradinių duomenų byloje įrašytos keturios eilutės, turinčios po keturis simbolius. Jos apibūdina situaciją žaidimo lentoje. 

Taškas „.“ atitinka tuščią lentos langelį, „x“ žymi neutralią šaškę, „#“ žymi pirmojo (jo eilė paeiti) žaidėjo L figūrą, „*“ žymi priešininko L figūrą. Duota situacija bus korektiška ir tokia, kad pirmasis žaidėjas galės padaryti bent vieną ėjimą.

REZULTATAI
Rezultatus įrašykite į bylą lgame.out. Jei egzistuoja laimintis ėjimas, išveskite jį tokiu pat formatu kaip pradiniu duomenų byloje. 

Priešingu atveju pirmoje rezultatų bylos eilutėje išveskite No winning move. Antroje eilutėje išveskite arba Draw, jei žaidimas baigsis lygiosiomis (laikant, kad abu žaidėjai žaidžia optimaliai), arba Losing, jei pirmasis žaidėjas pralaimės. 

PRADINIŲ DUOMENŲ IR REZULTATŲ PAVYZDŽIAI
Pradiniai duomenys 		Rezultatai 		
(lgame.in)			(lgame.out)

.***
x*#x
###.
....

.***
#*.x
###.
x...

(lgame.in)			(lgame.out)

No winning move
Draw

...x
###.
#***
x..*

(lgame.in)			(lgame.out)

No winning move 
Losing

.###
x#*x
***.
....

VERTINIMAS
Balai už testus, kuriuose neegzistuoja laimintis ėjimas bus skiriami tik tada, jei programa surinks bent pusę taškų už testus, kuriems egzistuoja laimintis ėjimas.