Koopamatk

면접 대비

시간 제한1초메모리 제한1024 MB

요약

격자에서 시작점에서 가장자리 출구까지의 최단 경로를 찾아 표시하고, 출구가 없으면 -1을 출력합니다.

난이도: 보통10점 중 4점
유형: BFS, 그래프, 행렬, 최단 경로
정답자: 아직 제출이 없습니다

문제

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 $H$ ja laius $W$ ( $1 \le H \le 100$ , $1 \le W \le 100$ ). Järgmisel $H$ real on igaühel täpselt $W$ märki: koobastiku kaart, kus '.' märgib läbipääsetavat kohta, '#' koopa seina ja '@' uurimisgrupi algasukohta. Punkt reas 1 või $H$ või veerus 1 või $W$ 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 $H$ 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$ ja esialgne kaart.

예제1

예제 1

입력

8 10
######.###
#........#
#.###.####
#.#...#..#
#.###.#.##
#.#......#
#.#@#.#..#
#.########

예상 출력

9
######*###
#....**..#
#.###*####
#.#..*#..#
#.###*#.##
#.#***...#
#.#@#.#..#
#.########