Kralj in dama

Osnovne informacije

Omejitve
  • Čas: 5 s
  • Spomin: 256 MB
Avtor:
  • Nino Bašić, Tomaž Hočevar
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Volim te slijepo, na svemu ti hvala,
al' ne živimo u istom svijetu.
Zato crni kralj i bijela dama,
nikad više u duetu.
― Dražen Zečić, Crni kralj i bijela dama

Na šahovnici višine V in širine S sta se znašla črni kralj in bela dama. Njuna začetna položaja sta takšna, da dama kralja ne napada (in seveda tudi kralj dame ne napada). Kralj in dama izmenično delata poteze, pri čemer začne dama. Premikata se po običajnih šahovskih pravilih. Dama bi rada kralja prisilila v šah-mat ali pat (tj. kralj ni v šahu, vendar ne more narediti veljavne poteze, po kateri ne bi bil v šahu), kralj pa bi se temu seveda rad izognil. Dama mora seveda paziti, da je kralj ne "poje".

Naloga

Napišite program, ki za podan začetni položaj kralja in začetni položaj dame izračuna maksimalno število potez (obeh igralcev skupaj) do trenutka, ko nastopi šah-mat oziroma pat ob optimalni igri obeh igralcev. Dama bi rada čimprej končala igro, kralj pa bi rad čim dlje zavlačeval.

Vhodni podatki

V prvi vrstici se nahajata dimenziji šahovnice, tj. števili V in S. Druga vrstica vsebuje število poizvedb P, ki sledijo v naslednjih vrsticah. Vsaka poizvedba je opisana s štirimi števili, ko so ločena s presledki: vrstica in stolpec kralja (v_k in s_k) ter vrstica in stolpec dame (v_d in s_d).

Omejitve vhodnih podatkov

  • 2 \leq V, S \leq 8
  • 1 \leq P \leq 3\;000
  • 1 \leq v_k, v_d \leq V
  • 1 \leq s_k, s_d \leq S

Izhodni podatki

Za vsako poizvedbo izpišite eno vrstico z iskanim številom potez ob optimalni igri. Če se lahko kralj izmika dami v neskončnost, izpišite KRUCIFIKS.

Primeri

Vhod

3 4
3
1 1 3 4
2 4 3 1
2 3 3 1

Izhod

1
3
7

Vhod

2 3
1
1 1 2 3

Izhod

KRUCIFIKS
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task