6122 : K번 텔레포트
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
벽과 빈칸으로 이루어진 미로에서 시작점 (0,0)에서 끝점 (N-1, M-1)까지 도달하려 합니다.
미로에는 순간이동 포털의 정보 P개가 주어지며, 지수는 포털 위치에 서 있는 경우 최대 K번까지 순간이동 포털을 사용하여 연결된 다른 포털 쌍 좌표로 1초 만에 이동할 수 있습니다. 최단 시간을 구하시오.
미로에는 순간이동 포털의 정보 P개가 주어지며, 지수는 포털 위치에 서 있는 경우 최대 K번까지 순간이동 포털을 사용하여 연결된 다른 포털 쌍 좌표로 1초 만에 이동할 수 있습니다. 최단 시간을 구하시오.
입력 설명
첫째 줄에 N, M (1 ≤ N, M ≤ 100), 최대 텔레포트 횟수 K (0 ≤ K ≤ 10)가 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 미로 격자가 주어집니다. (0은 빈칸, 1은 벽)
그 다음 줄에 포털 쌍의 수 P (0 ≤ P ≤ 20)가 주어지고, 이후 P개의 줄에 걸쳐 순간이동 양방향 포털의 위치 쌍
둘째 줄부터 N개의 줄에 걸쳐 미로 격자가 주어집니다. (0은 빈칸, 1은 벽)
그 다음 줄에 포털 쌍의 수 P (0 ≤ P ≤ 20)가 주어지고, 이후 P개의 줄에 걸쳐 순간이동 양방향 포털의 위치 쌍
r1 c1 r2 c2 정보가 주어집니다.출력 설명
시작점에서 끝점까지 도달할 수 있는 최소 시간을 출력합니다. 도달할 수 없으면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3 1
0 1 0
0 1 0
0 1 0
1
0 0 2 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1도움
상태 공간에 텔레포트 사용 횟수 차원을 추가하여 3차원 배열
dist[r][c][k_used]으로 최단 거리를 탐색하십시오.