5362 : B63 - 너비 우선 탐색
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
2차원 미로에서 시작 지점에서 도착 지점까지 가는 최소 이동 횟수를 구하십시오.
[제약 조건]
• $3 \le R, C \le 50$
• $R, C$ 는 정수
• $1 \le sy, sx \le R, C$
• $1 \le gy, gx \le R, C$
• 미로는 '#' (벽)과 '.' (통로)로만 구성됩니다.
[제약 조건]
• $3 \le R, C \le 50$
• $R, C$ 는 정수
• $1 \le sy, sx \le R, C$
• $1 \le gy, gx \le R, C$
• 미로는 '#' (벽)과 '.' (통로)로만 구성됩니다.
입력 설명
첫째 줄에 미로의 행 수 $R$, 열 수 $C$가 주어집니다.
둘째 줄에 시작 지점의 좌표 $sy, sx$, 셋째 줄에 도착 지점의 좌표 $gy, gx$가 주어집니다.
이후 $R$개 줄에 미로의 상태(통로 '.', 벽 '#')가 주어집니다.
둘째 줄에 시작 지점의 좌표 $sy, sx$, 셋째 줄에 도착 지점의 좌표 $gy, gx$가 주어집니다.
이후 $R$개 줄에 미로의 상태(통로 '.', 벽 '#')가 주어집니다.
출력 설명
최소 이동 횟수를 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7 8
2 2
4 5
########
#......#
#.######
#..#...#
#..##..#
##.....#
########
출력 예시
COPY
복사되었습니다!
복사되었습니다!
11도움
출력 예 3의 경우 더 이상 미로라고 부를 수 없는 넓은 공간이지만, 이 문제에서는 이러한 판도 미로로 취급합니다. 어쨌든 시작점에서 골인 지점까지의 최소 이동 횟수는 94입니다.