문제 설명: 당신은 마법사 '엘라'가 되어 미지의 차원을 탐험하고 있습니다. 이 차원은 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을 출력합니다.
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을 출력합니다.
예시:
입력 :
출력 :