동굴 탐사

스펠레올로지(동굴학)는 상상할 수 있는 학문 중에서도 특히 흥미롭고 모험이 많은 분야인 것은 분명하다. 물론 모험에는 위험도 따른다. 하지만 완전히 안전한 모험이 과연 있을까. 어쨌든 주의를 기울여도 땅속에서는 온갖 예상치 못한 일이 일어날 수 있고, 연구자들은 때때로 동굴에서 최대한 빨리 빠져나와야 한다.

그래서 어떤 출구로든 가는 최단 경로를 찾는 프로그램을 작성해야 한다.

파일의 첫 줄에 동굴 지도의 높이 $H$와 너비 $W$가 주어진다($1 \le H \le 100$, $1 \le W \le 100$). 다음 $H$줄에는 각각 정확히 $W$개의 문자가 있다. '.'은 지나갈 수 있는 칸, '#'은 동굴 벽, '@'은 조사팀의 출발 위치를 나타낸다. 1행, $H$행, 1열, $W$열에 있는 칸이 출구를 나타낸다.

연구자들은 매 걸음마다 같은 행이나 같은 열에 있는, 지나갈 수 있는 인접한 칸으로 이동할 수 있다.

파일의 첫 줄에 동굴에서 빠져나오는 가장 짧은 경로의 길이를 출력한다. 다음 $H$줄에는 그 경로를 별표('*')로 표시한 지도를 출력한다. 최단 길이의 경로가 여러 개라면 그중 아무거나 하나를 출력하면 된다. 출구가 없으면 -1을 출력하고, 원래 지도를 그대로 출력한다.