Žirgo ėjimas

Pradinių duomenų failas:

zirgas.in  

Rezultatų failas:

zirgas.out  

Laiko apribojimas:

2 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Šachmatai – tai labai senas žaidimas, žaidžiamas kvadratinėje 8×8 matmenų lentoje. Viena iš žaidimo figūrų yra žirgas, ir tai turbūt „įdomiausiai“ einanti figūra. Žirgo ėjimai pavaizduoti žemiau esančiame paveiksle:

Vienas iš galvosūkių, susijusių su žirgo figūra, yra nustatymas, kaip žirgo ėjimu apeiti visą šachmatų lentą taip, kad kiekvienas langelis būtų aplankytas lygiai vieną kartą. Parašykite programą, sprendžiančią šį uždavinį.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašyti trys sveikieji skaičiai N, S ir E. N – tai lentos dydis, t. y. lentos matmenys yra NxN (1 <= N < 8). S ir E – tai langelio, kuriame žirgas turi pradėti, atitinkamai, stulpelio ir eilutės numeriai (1 <= S, E <= N).

Rezultatai

Jei egzistuoja būdas žirgo ėjimu apeiti lentą pradėjus duotame langelyje, į rezultatų failą programa turi išvesti NxN matmenų skaičių lentelę, kurios langeliuose būtų surašyti skaičiai nuo 1 iki \(N^{2}\), žymintys, kuriuo ėjimu žirgas turi aplankyti kiekvieną langelį. Vienoje eilutėje skaičiai gali būti atskirti vienu ar daugiau tarpų. Jei yra keli sprendiniai, programa turi išvesti bet kurį. Jei nėra nei vieno sprendinio, pirmoje failo eilutėje programa turi įrašyti žodį NEIMANOMA.

Pavyzdžiai

5 3 3

 25 10 15  4 19
 16  5 18  9 14
 11 24  1 20  3
  6 17 22 13  8
 23 12  7  2 21

3 1 1

NEIMANOMA