7119 : 격자 경로 + 장애물
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N × M 크기의 격자가 주어집니다. 격자에 K개의 장애물이 존재합니다.
(0,0) 위치에서 출발하여 (N-1, M-1) 위치로 가는 최단 경로(오른쪽과 아래쪽으로만 이동)의 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
(0,0) 위치에서 출발하여 (N-1, M-1) 위치로 가는 최단 경로(오른쪽과 아래쪽으로만 이동)의 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 N, M, K가 공백으로 구분되어 주어집니다. (1 ≤ N, M ≤ 100, 0 ≤ K ≤ 100)
이후 K개의 줄에 걸쳐 각 장애물의 좌표
이후 K개의 줄에 걸쳐 각 장애물의 좌표
r c (0-indexed, 0 ≤ r < N, 0 ≤ c < M)가 주어집니다.출력 설명
장애물을 피해 목적지에 도달하는 최단 경로의 개수를
1,000,000,007로 나눈 나머지를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3 1
1 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
K개의 장애물 좌표를 저장한 뒤, DP 순회 시 장애물 칸의 값을 0으로 고정하여 최단 경로 개수를 누적합니다.