시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 468 | 131 | 39 | 21.311% |
토끼 마을을 모험하던 중학생 토끼 삼총사는 미로를 마주하게 되었습니다. 미로는 세로 길이 N, 가로 길이 M으로 N × M 격자 모양입니다. 격자의 각 칸은 위에서부터 i 번째, 왼쪽에서부터 j 번째 칸을 (i, j)로 표기합니다. 따라서 맨 왼쪽 위 칸은 (1, 1)이고, 맨 오른쪽 아래 칸은 (N, M)입니다. 미로의 일부 칸에는 벽이 있을 수도 있습니다. 단, (1, 1)과 (N, M)에는 언제나 벽이 없습니다.
삼총사는 미로를 통과하기 위해 (1, 1)에서 (N, M)까지 가장 적은 이동 횟수로 이동하고자 합니다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸입니다. 단, 벽이 있는 칸으로는 이동할 수 없습니다.
삼총사 중에서 장래희망이 바리스타인 파랑 토끼는 특별한 기술 “바리스타의 힘”을 사용할 수 있습니다. 어떤 칸에서 상하좌우 중 한 방향을 정해서 기술을 사용하면 해당 방향에 있는 모든 칸들의 벽이 사라집니다. 원래 벽이 없는 칸에는 아무 일도 일어나지 않습니다. 다만, 기술을 너무 남용하면 모험이 시시해지므로 “바리스타의 힘”은 최대 한 번까지만 사용하기로 했습니다.
미로의 지도가 주어지면, (1, 1)에서 (N, M)까지 이동할 때 이동 횟수의 최솟값을 구해봅시다.
첫 번째 줄에 두 개의 자연수 N와 M가 주어집니다. (1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000)
두 번째 줄부터 N 개의 줄에 각 줄마다 0
과 1
로만 이루어진 길이 M의 문자열이 한 개씩 주어집니다.
i + 1 번째 줄 j 번째 문자가 0
이면 (i, j)에 벽이 없다는 뜻이고, 1
이면 있다는 뜻입니다. (1, 1)과 (N, M)에 벽이 없는 입력만 주어집니다.
첫 번째 줄에 이동 횟수의 최솟값을 출력합니다. 만약, 미로를 통과할 수 없다면 -1
을 출력합니다.
4 7 0000010 1101010 1001110 1100110
9
가능한 방법으로 (1, 1)에서 (1, 2), (1, 3)을 거쳐 (2, 3)까지 이동한 다음, 오른쪽 방향으로 “바리스타의 힘”을 사용하여 (2, 4)와 (2, 6)에 있는 벽을 사라지게 하고, 다시 (2, 3)에서 (2, 4), (2, 5), (2, 6), (2, 7), (3, 7)을 거쳐 (4, 7)로 이동하는 방법이 있습니다.
7 5 00010 01010 01001 01100 10001 00110 10000
10
6 8 00001100 01101001 00110001 10101010 01000111 01001000
-1
5 5 01000 00010 11100 10001 00110
10