8033 : 격자 경로 DP
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N \times N$ 크기의 격자가 주어집니다. 격자의 각 칸은 비어 있거나(
[제약 조건]
• $1 \le N \le 1{,}000$
• 격자의 각 칸은 빈칸(
.) 장애물(*)이 있습니다. 좌측 상단 $(1,1)$ 칸에서 출발하여 우측 하단 $(N,N)$ 칸까지 도달하고자 합니다. 오직 아래와 오른쪽 방향으로만 이동이 가능하고 장애물이 있는 칸은 지나갈 수 없다고 할 때, 가능한 서로 다른 경로의 개수를 구하는 프로그램을 작성하시오.[제약 조건]
• $1 \le N \le 1{,}000$
• 격자의 각 칸은 빈칸(
.) 또는 장애물(*)입니다.입력 설명
첫째 줄에 격자의 크기 $N$이 주어집니다. ($1 \le N \le 1000$)
다음 $N$개의 줄에 걸쳐 격자의 상태가 각 줄마다 $N$개의 문자로 주어집니다.
다음 $N$개의 줄에 걸쳐 격자의 상태가 각 줄마다 $N$개의 문자로 주어집니다.
출력 설명
도달 가능한 경로의 개수를 $10^9+7$로 나눈 나머지를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
....
.*..
...*
*...
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
격자 상에서 $(i,j)$ 칸까지 도달하는 경로의 수 $dp[i][j]$는 위쪽 칸에서 내려오는 경우와 왼쪽 칸에서 오른쪽으로 오는 경우의 합입니다. 즉, 격자가 비어 있을 때 $dp[i][j] = (dp[i-1][j] + dp[i][j-1]) \pmod{10^9+7}$ 이며, 격자가 장애물(
*)인 경우 $dp[i][j] = 0$ 입니다. 초기값 $dp[1][1] = 1$ (단, 시작칸이 비어있는 경우)로 시작하여 이중 루프를 통해 $O(N^2)$ 시간에 해결할 수 있습니다.