Pazemes alas

ID: alas
Grūtība: 3/5
Laika limits: 3

Uzdevums

Speleoloģija noteikti ir interesanta un piedzīvojumiem bagāta zinātne, bet dažreiz piedzīvojumi var kļūt bīstami. No otras puses, ja viss būtu pilnīgi droši, tad nebūtu īstu piedzīvojumu... Jebkurā gadījumā, par spīti visiem drošības pasākumiem, ko speleologi ievēro, pazemē var notikt daudzas daz'ādas lietas. Tāpēc dažkārt ir svarīgi tikt ārā no alas cik ātri vien iespējams. Jums jāuzraksta programma, kas speleologiem palīdz atrast īsāko cel'u līdz izejai.

 

Ievaddati

Teksta faila alas.in pirmajā rindā doti divi naturāli skaitļi - alas augstums H (H<100) un platums W(W<100), kas atdalīti ar tukšumsimbolu.
Nākošajās H faila rindās katrā atrodas tieši W simboli, kas kopā veido alas karti.
Gaiteņi attēloti ar tukšumsimboliem, bet sienas ar simbolu # . Grupas sākotnējās atrašanās vieta apzīmēta ar @ . Tukšumsimbols pirmajā vai H-tajā rindā vai arī pirmajā vai W-tajā kolonnā apzīmē izeju.

 

Izvaddati

Teksta failā alas.out jāizvada īsākā ceļa garums līdz izejai, kā arī karte, kurā maršruts attēlots ar zvaigznītēm (*). (Vai arī mars'ruta garums jāizvada kā -1 un karte bez zvaigznītēm, ja no dotā labirinta izejas nav.)
Atcerieties, ka gājieni atl'auti tikai vertikālā un horizontālā virzienā.

 

Piemērs

alas.inalas.out
8 10
###### ###
#        #
# ### ####
# #   #  #
# ### # ##
# #      #
# #@# #  #
# ########
9
######*###
#    **  #
# ###*####
# #  *#  #
# ###*# ##
# #***   #
# #@# #  #
# ########

 

Atsauces

Uzdevums izmantots "Baltijas algoritmizācijas skolas" projektā, kas tika organizēts ar "Sorosa fonds-Latvija" atbalstu 1996.gadā.
© 2001-2002 olimps! http://www.lio.lv/olimps/