sinderella   1년 전

문제공지 후 1일 내에 정답 공개합니다. 문제 풀어서 적어보세요!

난이도-상

문제 설명:
당신은 마법사 '엘라'가 되어 미지의 차원을 탐험하고 있습니다. 이 차원은 N×M 크기의 격자 지형으로 이루어져 있으며, 각 칸은 일반 지형, 시작점, 도착점, 또는 순간이동 지점 중 하나입니다.

엘라는 일반 지형을 이동할 때는 한 칸당 1의 마나를 소모합니다. 상하좌우 네 방향으로만 이동할 수 있습니다.

엘라는 특별한 능력이 있는데, 바로 순간이동(텔레포트) 마법입니다. 이 마법은 다음 규칙을 따릅니다:

**순간이동 지점(T)**에 있을 때만 마법을 사용할 수 있습니다.
순간이동 마법을 사용하면, 현재 있는 순간이동 지점에서 다른 어떤 순간이동 지점으로도 즉시 이동할 수 있습니다.
순간이동 마법을 한 번 사용할 때마다 **고정 마나 소모량 (TELEPORT_FIXED_COST)**과 현재 지점부터 도착 지점까지의 맨해튼 거리만큼의 마나를 추가로 소모합니다. (맨해튼 거리: ∣x_1−x_2∣+∣y_1−y_2∣)
엘라는 최대 K번만 순간이동 마법을 사용할 수 있습니다.
엘라의 목표는 시작점(S)에서 도착점(E)까지 최소 마나 소모량으로 도달하는 것입니다. 만약 도착점에 도달하는 것이 불가능하다면 -1을 출력합니다.

입력:

첫째 줄에 정수 N,M,K가 공백으로 구분되어 주어집니다. (1≤N,M≤50, 0≤K≤5)
둘째 줄에 정수 TELEPORT_FIXED_COST가 주어집니다. (1≤TELEPORT_FIXED_COST≤100)
다음 N개의 줄에 걸쳐 M개의 문자로 이루어진 격자 지형이 주어집니다.
. : 일반 지형
S : 시작점 (항상 하나만 존재)
E : 도착점 (항상 하나만 존재)
T : 순간이동 지점 (여러 개 있을 수 있으며, 없을 수도 있음)
출력:

시작점에서 도착점까지 도달하는 최소 마나 소모량을 출력합니다.
만약 도착점에 도달할 수 없다면 -1을 출력합니다.

예시:

입력 :

5 5 1
10
S.T.E
.....
.T...
.....
.....

출력 :

4

jtw7913   1년 전

질문드립니다. 예제 정답이 왜 15인가요? 꼭 텔레포트를 해야하지 않아도 되지않나요? 그럼 4(T에서 텔레포트 안쓰고 자날수 있다면) or 6(T에서 텔레포트를 무조건 써야한다면)이 아닌가요?

sinderella   1년 전

@jtw7913님

죄송합니다. 15가 아니라 4입니다. 오류가 있었습니다 ㅜㅜ

sinderella   1년 전

정답 공지해드리도록 하겠습니다.

일단 C언어 공개 뒤 다른 언어도 질문해주세요.

댓글을 작성하려면 로그인해야 합니다.