6121 : 벽 부수기 최단
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×M 크기의 격자 미로에서 (1,1)에서 (N,M)까지 이동하는 최단 거리를 구하십시오. 0은 이동 가능, 1은 벽입니다.
다만, 이동 효율성을 극대화하기 위해 이동하는 도중 최대 1개까지의 벽을 부수고 지나갈 수 있습니다. 최단 거리를 구하시오.
다만, 이동 효율성을 극대화하기 위해 이동하는 도중 최대 1개까지의 벽을 부수고 지나갈 수 있습니다. 최단 거리를 구하시오.
입력 설명
첫째 줄에 N과 M (1 ≤ N, M ≤ 1,000)이 주어집니다.
둘째 줄부터 N개의 줄에 미로 격자가 공백 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 미로 격자가 공백 구분되어 주어집니다.
출력 설명
시작점과 도착점을 포함한 최단 거리를 출력합니다. 도달 불가 시 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
0 1 0
0 1 1
0 0 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5도움
방문/거리 배열에 벽을 부쉈는지 여부를 상태 차원에 포함하여
visited[r][c][broken_state]와 같이 3차원으로 설계하고 BFS 탐색을 하십시오.