Najkraći put
Opis zadatka:
U ulaznoj tekstualnoj datoteci nalazi se pravougaona matrica veličine
M x N gdje je M širina, a
N visina polja. Matrica se sastoji isključivo od brojeva 0 i 1,
gdje 0 označava prazno polje, a 1 označava zid, tj. polje koje nije prohodno.
Potrebno je napraviti program koji nalazi dužinu najkraćeg put između tačaka
(X1,Y1) i (X2,Y2), ili prijavljuje da takav put
ne postoji. Kretanje je moguće samo po poljima na kojima se nalazi simbol 0, s tim da je
kretanje moguće samo u 4 pravca, tj. lijevo, desno, gore, dolje, po jedno polje (što se
računa kao jedan korak). Kretanje nije moguće u bilo kojem dijagonalnom smjeru. Ako postoji
više puteva koji su najkraći, potrebno je ispisati dužinu samo jednog od njih, jer svi
ostali također moraju imati istu dužinu.
Kao primjer posmatrajmo slijedeću matricu:
(1,1) (5,1)
(1,1) 0 0 0 0 0
0 0 1 0 0
0 1 1 0 0
0 0 1 1 0
0 0 1 0 0
(1,6) 0 0 0 0 0
Neka početno polje ima koordinate (2,4), a krajnje polje koordinate (4,3). Ova polja su na
slici označena podcrtano. Na slici su podebljano označena 2 moguća najkraća puta, a za oba
je dužina puta 9, što predstavlja traženo rješenje.
U direktoriju sa zadacima treba da se nalazi izvršni kod programa i to pod imenom
PUT.EXE.
Ulazna datoteka:
U tekućem direktoriju će se nalaziti datoteka PUT.IN tekstualnog formata
koja sadrži N+3 linija.
U prvoj liniji se nalaze brojevi M i N
(1 <= M,N <= 100), odnosno širina i visina polja, odvojeni jednim
blanko znakom.
Drugi red ulazne datoteke sadrži brojeve
X1 i Y1 (1 <= X1,Y1 <=100),
odnosno poziciju početnog polja, pri čemu su koordinate odvojene jednim blanko znakom.
U trećem redu se nalaze brojevi X2 i Y2
(1 <= X2,Y2 <= 100),
odnosno pozicija krajnjeg polja, pri čemu su koordinate također odvojene jednim blanko znakom.
Od četvrtog do N+3-og reda u svakom redu će se nalaziti
M karaktera, isključivo znakova 1 i 0, koji nisu odvojeni
nikakvim razmacima, a koji predstavljaju redove u pravougaonom polju.
Nije potrebna nikakva kontrola ispravnosti ulaznih podataka. Brojvi će uvijek biti u navedenim
granicama, a početna i krajnja pozicija će uvijek biti pozicija na kojoj se nalazi simbol 0.
Izlazna datoteka:
Program treba da napravi u tekućem direktoriju izlaznu datoteku PUT.OUT, tekstualnog formata.
Datoteka treba da sadrži samo jedan red u kojem će se nalaziti samo jedan broj,
koji predstavlja dužinu najkraćeg puta. Ako od početne do krajnje tačke nema "prohodnog" puta,
datoteka treba da sadrži jednu liniju u kojoj će pisati velikim slovima:
PUT NE POSTOJI
Vremensko ograničenje:
Za svaki testni primjer program treba da ponudi rješenje za najviše 10 sekundi.
Primjeri:
PUT.IN
5 6
2 4
4 3
00000
00100
01100
00110
00100
00000
PUT.OUT
9
Ove datoteke odgovaraju primjeru datom u postavci zadatka.
[Rješenje (Pascal)]
[Rješenje (C++)]