CSES 3. Grid Paths (1638)

출처: https://cses.fi/problemset/task/1638

---

문제 설명

Consider an N x N grid whose squares may have traps. It is not allowed to move to a square with a trap.

Your task is to calculate the number of paths from the upper-left square to the lower-right square where you only can move right or down.

입력  

First line: N /// grid size

N line : grid information ( . : empty cell, * : trap)

출력

Print the number of paths modulo 1e9 + 7

입력 예

4
....
.*..
...*
*...

출력 예

3

제약조건

1 <= N <= 1000

---

문제 풀이 내용

어떤 특정한 cell ( path[i][j] ) 까지 도착하는 경로는 왼쪽에서 온 경우( path[i-1][j])와 위쪽에서 온 경우(path[i][j-1])의 합으로 결정된다. 제일 처음 출발하는 cell부터 목표로 하는 cell 까지 cell이 trap(*)인 경우는 제외하고 더해서 만들어 간다. 

프로그램 내용

...
    vector <string> maze(n+1);
    for (int i = 1; i <= n; i++)
        string tmp;
        maze[i] = "."+tmp;

    vector <vector<int>> path(n+1, vector<int>(n+1));

    path[1][0] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (maze[i][j] == '.')
                path[i][j] = (path[i-1][j]+path[i][j-1]) % M;
...

 

Dynamic Programming ( link )