6131 : 캐릭터 이동
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×M 크기의 2D 격자 맵에서 시작 좌표 (r1, c1)에서 도착 좌표 (r2, c2)로 이동하는 최단 거리를 구하시오.
0은 빈칸이고 1은 장애물입니다. 캐릭터는 평소에는 상하좌우 인접한 1칸을 이동(장애물 이동불가)하지만, 최대 K번까지 장애물을 뛰어넘는 2칸 특수 점프를 수행할 수 있습니다. (점프의 목적지 격자는 빈칸(0)이어야 하며, 중간 경로는 벽이어도 상관없습니다.)
0은 빈칸이고 1은 장애물입니다. 캐릭터는 평소에는 상하좌우 인접한 1칸을 이동(장애물 이동불가)하지만, 최대 K번까지 장애물을 뛰어넘는 2칸 특수 점프를 수행할 수 있습니다. (점프의 목적지 격자는 빈칸(0)이어야 하며, 중간 경로는 벽이어도 상관없습니다.)
입력 설명
첫째 줄에 N과 M (1 ≤ N, M ≤ 100)이 주어집니다.
둘째 줄부터 N개의 줄에 미로 격자가 공백 구분되어 주어집니다.
마지막 줄에는 시작 r1 c1, 도착 r2 c2, 그리고 사용 가능한 점프 횟수 K (0 ≤ K ≤ 5)가 공백 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 미로 격자가 공백 구분되어 주어집니다.
마지막 줄에는 시작 r1 c1, 도착 r2 c2, 그리고 사용 가능한 점프 횟수 K (0 ≤ K ≤ 5)가 공백 구분되어 주어집니다.
출력 설명
목표 위치에 도달하는 최소 이동 횟수를 출력합니다. 도달할 수 없으면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
0 1 0
0 1 0
0 0 0
0 0 0 2 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1도움
점프 횟수를 상태 차원에 포함하여
visited[r][c][jump_count]를 활용한 BFS를 수행하십시오.