Koopamatk

문제

Speleoloogia on kahtlemata üks põnevamaid ja seiklusrikkamaid teadusi, mida on võimalik üldse ette kujutada. Muidugi kaasnevad seiklustega ka ohud. Aga ega üks päris ohutu asi ikka seiklus ei ole ka ju... Nii või naa, ettevaatusabinõudele vaatamata võib maa all igasuguseid ootamatusi juhtuda ja vahel on teadlastel vaja koobastest välja jõuda nii kiiresti kui vähegi võimalik.

Selleks ongi tarvis kirjutada programm, mis leiaks lühima tee mõne väljapääsuni.

입력

Faili esimesel real on koobastiku kaardi kõrgus $HH$ ja laius $WW$ ($1\le H\le 1001\; \backslash le\; H\; \backslash le\; 100$, $1\le W\le 1001\; \backslash le\; W\; \backslash le\; 100$). Järgmisel $HH$ real on igaühel täpselt $WW$ märki: koobastiku kaart, kus '.' märgib läbipääsetavat kohta, '#' koopa seina ja '@' uurimisgrupi algasukohta. Punkt reas 1 või $HH$ või veerus 1 või $WW$ märgib väljapääsu. Teadlased saavad igal sammul liikuda läbipääsetavale naaberruudule samas reas või samas veerus.

출력

Faili esimesele reale väljastada lühima koopast välja viiva tee pikkus ja järgmisele $HH$ reale kaart, millel see tee on märgitud tärnidega ('*'). Kui minimaalse pikkusega teid on mitu, väljastada ükskõik milline neist. Kui väljapääsu ei ole, väljastada arv $-1-1$ ja esialgne kaart.