6128 : 미로 — 최단+최다
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×M 크기의 격자 지도에서 시작점 (r1, c1)에서 도착점 (r2, c2)까지 가는 최단 경로의 길이와, 그 길이를 가지는 서로 다른 최단 경로의 총 개수를 구하는 프로그램을 작성하십시오.
0은 이동 가능, 1은 벽입니다. 경로의 길이는 지나간 칸의 개수(시작점과 도착점 포함)로 정의합니다.
0은 이동 가능, 1은 벽입니다. 경로의 길이는 지나간 칸의 개수(시작점과 도착점 포함)로 정의합니다.
입력 설명
첫째 줄에 N, M (1 ≤ N, M ≤ 20)이 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 격자 정보가 공백 구분되어 주어집니다.
마지막 줄에는 시작 좌표 r1, c1과 끝 좌표 r2, c2가 공백으로 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 격자 정보가 공백 구분되어 주어집니다.
마지막 줄에는 시작 좌표 r1, c1과 끝 좌표 r2, c2가 공백으로 구분되어 주어집니다.
출력 설명
첫째 줄에 최단 경로 길이를 출력하고, 둘째 줄에 최단 경로의 개수를 출력합니다. 도달할 수 없다면 첫째 줄에 -1, 둘째 줄에 0을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
0 0 0
0 1 0
0 0 0
0 0 2 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5
2도움
BFS로 시작점부터 각 칸까지의 최단 거리를 기록하고, 거리 순서대로 노드를 정렬하여
ways[next] += ways[curr] 와 같은 DP(동적 계획법) 테이블 갱신을 적용하면 최단 경로의 가짓수를 누적할 수 있습니다.