Nosaukums
Pazemes alas (alas)
Laika limits
3.00s
Atmiņas limits
256.0 MB
Grūtība
50%

Definīcija

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.


Ievaddatu raksturojums

Ievaddatu 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.


Izvaddatu raksturojums

Izvaddatos 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ā.


Piezīmes

Uzmanību: testa datos jaunas rindas ir kodētas nekonsistenti gan windows stila "\r\n" gan UNIX stila "\n".

Uzdevums izmantots "Baltijas algoritmizācijas skolas" projektā, kas tika organizēts ar "Sorosa fonds-Latvija" atbalstu 1996.gadā.


Paraugdati

Stdin
8 10
###### ###
#        #
# ### ####
# #   #  #
# ### # ##
# #      #
# #@# #  #
# ########
Stdout
9
######*###
#    **  #
# ###*####
# #  *#  #
# ###*# ##
# #***   #
# #@# #  #
# ########

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