6109 : 격자 BFS
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×M 크기의 격자 맵 정보가 주어집니다. 0은 이동할 수 있는 빈칸이고, 1은 벽으로 막혀 지나갈 수 없습니다.
시작 좌표 (r1, c1)에서 출발하여 도착 좌표 (r2, c2)까지 상하좌우로만 이동할 수 있을 때, 도달하는 데 필요한 최소 이동 칸 수를 구하는 프로그램을 작성하십시오.
시작 좌표 (r1, c1)에서 출발하여 도착 좌표 (r2, c2)까지 상하좌우로만 이동할 수 있을 때, 도달하는 데 필요한 최소 이동 칸 수를 구하는 프로그램을 작성하십시오.
입력 설명
첫째 줄에 격자의 세로 크기 N과 가로 크기 M (1 ≤ N, M ≤ 1,000)이 주어집니다.
둘째 줄부터 N개의 줄에 격자의 정보가 공백 구분되어 주어집니다.
마지막 줄에는 시작 좌표 r1, c1과 끝 좌표 r2, c2가 공백으로 구분되어 주어집니다. (0-indexed)
둘째 줄부터 N개의 줄에 격자의 정보가 공백 구분되어 주어집니다.
마지막 줄에는 시작 좌표 r1, c1과 끝 좌표 r2, c2가 공백으로 구분되어 주어집니다. (0-indexed)
출력 설명
시작 좌표에서 끝 좌표까지 도달 가능한 최소 이동 거리를 출력합니다. 도달할 수 없으면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
0 1 0
0 1 0
0 0 0
0 0 0 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
6도움
2차원 격자 상에서 상하좌우 4방향에 대한 이동 변이
dr = [-1, 1, 0, 0], dc = [0, 0, -1, 1]을 정의하고, 큐와 2차원 방문/거리 배열을 이용해 탐색을 수행하십시오.