Nosaukums
Labirints un maģija (maglab)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
56%

Definīcija

Lai nonāktu pie dzīvā ūdens avota, ceļiniekam jāiziet cauri labirintam. Ne vienmēr tas ir izdarāms bez maģijas pielietošanas. Maģija ļauj ceļiniekam iet cauri labirinta sienām. Diemžēl maģiju var pielietot ierobežotu reižu skaitu, bet līdz avotam jānonāk pēc iespējas ātrāk.

Labirintam ir kvadrātveida forma un tas sastāv no N*N rūtiņām. Katru rūtiņu var viennozīmīgi noteikt ar tās koordinātām (rindas_numurs, kolonnas_numurs). Pa rūtiņu malām var būt izvietotas sienas.

Katrā brīdī ceļinieks var atrasties tieši vienā rūtiņā. Vienā solī ceļinieks var pārvietoties uz rūtiņu, kurai ar pašreizējo ir kopīga mala. Ceļinieks K reizes var iet cauri sienām un nevar iziet ārpus labirinta robežām.

Uzrakstiet programmu, kas nosaka, ar kādu mazāko soļu skaitu ceļinieks var nonākt rūtiņā ar koordinātām (P,Q), sākot ceļu rūtiņā (1,1)!


Ievaddatu raksturojums

Ievaddatu pirmā rinda satur naturālus skaitļus N, K, P, Q (2<=N<=200, 0<=K<=250, 1<=P,Q<=N). Nākošā N-1 rinda satur pa N veseliem skaitļiem - horizontālo sienu pazīmes. Nākošās N rindas satur pa N-1 skaitlim - vertikālo sienu pazīmes. Pazīme ir 0, ja attiecīgajā vietā sienas nav, vai 1, ja siena ir.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada vesels skaitlis - mazākais soļu skaits, ar kādu ceļinieks var no rūtiņas (1,1) nonākt rūtiņā (P,Q). 


Piezīmes

Zīmējums testpiemēram:

 

Uzdevums izmantots Ukrainas XIV informātikas olimpiādē 2001.gadā.


Paraugdati

Stdin
3 1 2 3
0 0 0
0 1 0
1 0
1 0
0 0
Stdout
3

Stdin
3 1 2 3
0 0 0
0 1 0
1 0
1 0
0 0
Stdout
3

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.