Informatica Online Judge

  Maze [0426 / 01AA]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 22   Total Tried : 40


The Champion of this Problem (C++) : sky1357koi - 0ms / 1662byte
My Best Submission (C++) : N/A

[]

Background

지난 가을 경곽이는 그의 연구실에서 미로를 개발했다. 이 미로는 여느 다른 미로와는 전혀 다른 특징이 있다. 그 특성은 물리적인 중력장을 이용한 워프존이 있다는 것이다. 이 워프존은 다른 워프존으로 실험용 쥐를 텔레포트 시키는 역할을 할 수 있다.

이 워프존은 양 방향으로 이동이 가능하다. 즉 출발워프존에서 도착워프존으로 텔레포트 할 수 있고 반대 방향으로도 워프할 수 있다.

이 미로는 출구를 제외하고는 외부와 연결된 통로가 없다.

경곽이가 개발한 이 미로는 N*M(2<=N,M<=300)의 직사각형으로 구성된다. 각 영역은 아래와 같은 요소로 구성된다.

- 벽 : 벽은 #으로 표시되며 실험용 쥐가 통과할 수 없다.
- 길 : 길은 .으로 표시되며 실험용 쥐가 쉽게 다닐 수 있다.
- 워프포인트 : 워프포인트는 대문자(A~Z)로 표시되며 다른 쪽의 같은 글자가 적힌 장소로 워프하며, 워프에 걸리는 시간은 0이다.
- 출구 : 출구는 미로를 탈출할 수 있는 유일한 장소이다. = 로 표시된다.
- 실험용 쥐 : 실험용쥐는 미로상의 길 위에서 출발한다. 쥐는 ‘@’로 표시된다.

경곽이는 실험용쥐가 미로의 임의의 위치에 있을 때, 탈출할 수 있는 가장 짧은 이동거리를 알고 싶어졌다. 다음 예를 보자. 다음은 n=5, m=6인 미로의 한 예이다.

###=##
#.W.##
#.####
#.@W##
######


이 경우 실험용 쥐는 처음에 오른쪽으로 1칸 옮겨 워프하여, 다시 오른쪽으로 1칸, 위로 1칸 가면 탈출할 수 있다. 따라서 총 이동거리 3이다. 이 보다 더 좋은 전략은 존재하지 않는다. 이러한 최소 이동거리를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 n과 m이 공백으로 구분되어 주어진다.
다음 줄부터 n줄에 걸쳐서 길이가 m인 문자열이 주어진다. 이 문자열은 각 미로의 요소들을 나타낸다.

Output

탈출하는데 필요한 최소 이동거리를 첫 번째 줄에 출력한다.

IO Example

입력
5 6
###=##
#.W.##
#.####
#.@W##
######


출력
3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]