프로그래머스 - 등굣길 c++

문제요약

    1. 격자 크기 (m x n)가 주어지고, 집에서 학교까지 오른쪽 또는 아래만 이동할 수 있습니다.

    2. 일부 지역은 물에 잠겨서 지나갈 수 없습니다.

    3. (1,1)에서 학교 (m, n) 까지 갈 수 있는 최단 경로의 개수를 계산해야 합니다.

    4. 결과값은 매우 클 수 있으므로, 1,000,000,007로 나눈 나머지 반환

 

1. 격자에서 이동 경로 (x+1, y) 또는 (x, y+1)로만 갈 수 있습니다. 

2. puddles에 해당하는 좌표는 이동 불가 하기 때문에 경로 계산에 포함 x

3.  경로의 개수를 세는 것이 목표

 

 

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
  const int MOD = 1000000007;


    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    dp[1][1] = 1; 


    for (auto& puddle : puddles) {
        int x = puddle[0];
        int y = puddle[1];
        dp[y][x] = -1;
    }


    for (int y = 1; y <= n; y++) {
        for (int x = 1; x <= m; x++) {
  
            if (dp[y][x] == -1) {
                dp[y][x] = 0;
                continue;
            }

     
            if (y > 1) dp[y][x] = (dp[y][x] + dp[y - 1][x]) % MOD;

            if (x > 1) dp[y][x] = (dp[y][x] + dp[y][x - 1]) % MOD;
        }
    }

    return dp[n][m];
}