Informatica Online Judge

  애퍼처 사이언스 [1983 / 07BF]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 8   Total Tried : 5


The Champion of this Problem (C++) : icp1481 - 15ms / 1888byte
My Best Submission (C++) : N/A

[?]

Background

사악한 A.I 글라도스는 R행과 C열의 미로에 케이크 두었다. 현수는 Aperture Science 포털건을 사용하여 케이크의 위치로 가야한다.

벽 "#"
빈공간 "."
당신의 위치 "S"
케이크 위치 "C"

빈공간은 걸어서 지나 갈수 있으며 지도 밖으로는 나갈 수 없다.

당신은 언제든지 포털건으로 위, 아래,오른쪽, 왼쪽 네 방향 중 하나로 포털을 쏠 수 있다.

당신이 쏜 포털은 첫 번째 벽에 도달할 때까지 그 방향으로 날아간다. 이 때 포털은 당신과 마주보고 있는 벽면에 생긴다.

포털은 지도에 최대 2개가 존재할 수 있다.다른 위치에서 포털을 각 각 하나씩 만들 수도 있다.

두 개의 포털이 이미 미로에 배치 된 경우 포털건을 다시 사용하면 기존 두 개 포털 중 하나(사용자가 선택)는 즉시 제거된다.

기존 포털에 포털을 발사하면 포털이 대체된다. 벽면의 측면 당 최대 하나의 포털이 있을 수 있으며, 동일한 벽 블록의 다른 측면에 두 개의 포털이 있을 수 도 있다.

미로에 두 개의 포털이 배치되어 있으면, 포탈 중 하나에 들어가 다른 포털로 나올 수 있다. 포털을 발사하는 데 시간이 걸리지 않으며 두 인접한 빈공간 사이를 이동하거나 포털을 통해 순간 이동하는데 1의 시간이 걸린다.

시작 지점, 케이크 위치, 미로의 지도가 주어지면, 케익에 도달하는 데 필요한 최소 시간을 계산하라.

Input

1이상 1000이하의 R,C가 주어지며 그 후 지도가 입력된다.
S,C는 정확히 한 번만 나타남을 보장한다.

Output

현수가 시작위치에서 케이크까지 가는데 걸리는 시간을 계산하시오.
항상 케이크로 갈 수 있음을 보장한다.
1

IO Example

입력

4 4
C.#.
#.#.
....
...S

출력
4

설명



왼쪽 2칸이동(2), 포털 두 개 생성(0),포털로 순간이동(1), 왼쪽으로 1칸 이동(1)
총 4시간 걸림

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