ŠIOM — Žaidimas

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1997_3e2_zaidimas_vyr.in

Rezultatų failas: lmio_1997_3e2_zaidimas_vyr.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Žaidimas

Duota kryžiaus formos lenta, turinti n(n+4m) langelių. Paveiksle pateiktas lentos pavyzdys, kai $n=3$ ir $m=2$ .

< insert image here >

Kai kuriuose lentos langeliuose yra juodos šaškės. Šaškių padėtis nusakoma koordinatėmis. Koordinačių pradžia laikomas centrinis langelis, jo koordinatės $(0;0)$ . Šaškės eina tik kirsdamos vertikaliai arba horizontaliai. Šaškė nukertama, jei per ją peršoka kuri nors kita šaškė (šokama tik į laisvą langelį).

Užduotis

Žaidimo tikslas – rasti tokią kirtimų seką, kad lentoje liktų tik viena šaškė. Parašykite algoritmą šiam tikslui pasiekti.

Pradiniai duomenys

Pirmoje eilutėje yra skaičiai $m$ ir $n$ ( $n$ – nelyginis), nusakantys lentos dydį. Antroje eilutėje – šaškių, esančių lentoje, skaičius $k$ . Kitose $k$ eilučių yra visų šaškių koordinatės (po du skaičius kiekvienoje eilutėje).

Rezultatai

Jei ieškomos kirtimų sekos negalima rasti, tai rašykite žodį NEGALIMA. Kitaip kiekvienoje eilutėje turi būti 4 skaičiai: kertančios šaškės koordinatės ir langelio, į kurį ta šaškė nušoka po kirtimo, koordinatės

Pavyzdžiai

Pradiniai duomenys	Rezultatai
2 3 10 0 0 1 0 2 0 3 0 1 1 -1 1 1 -1 -1 -1 -2 0 -3 0	-3 0 -1 0 -1 0 -1 -2 1 0 1 -2 3 0 1 0 1 1 1 -1 1 -2 1 0 1 0 -1 0 -1 1 -1 -1 -1 -1 -1 -3

Ribojimai

$m\\leq5$

$n\\leq5$