7106 : 경우의 수 — 경로
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N × M 크기의 격자가 주어집니다. 격자의 각 칸은 빈칸(0)이거나 장애물(1)입니다.
(0,0) 위치에서 출발하여 오른쪽과 아래쪽으로만 이동하여 (N-1, M-1) 위치로 가는 최단 경로의 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
(0,0) 위치에서 출발하여 오른쪽과 아래쪽으로만 이동하여 (N-1, M-1) 위치로 가는 최단 경로의 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 격자의 세로 크기 N과 가로 크기 M이 주어집니다. (1 ≤ N, M ≤ 100)
둘째 줄부터 N개의 줄에 걸쳐 각 줄에 M개의 숫자가 공백으로 구분되어 주어집니다. 0은 지나갈 수 있는 길, 1은 지나갈 수 없는 장애물을 의미합니다.
둘째 줄부터 N개의 줄에 걸쳐 각 줄에 M개의 숫자가 공백으로 구분되어 주어집니다. 0은 지나갈 수 있는 길, 1은 지나갈 수 없는 장애물을 의미합니다.
출력 설명
출발지에서 도착지까지 가는 경로의 총 개수를
1,000,000,007로 나눈 나머지를 출력합니다. (경로가 존재하지 않거나 출발지/도착지가 장애물인 경우 0을 출력합니다.)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
0 0 0
0 1 0
0 0 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
기본 격자 DP 문제입니다.
dp[i][j] = dp[i-1][j] + dp[i][j-1] 이며, 장애물(1)이 있는 칸은 dp[i][j] = 0으로 처리합니다.