[コードテストC+]通学路

今日の質問

通学路

私の答え

#include <string>
#include <vector>
using namespace std;

int solution(int n, int m, vector<vector<int>> puddles) {

    if(m == 1 || n == 1){
        if(puddles.size()!= 0)
            return 0;
        else
            return 1;
    }
    vector<vector<long long>> dp(m, vector<long long>(n, 0));
    
    for(int i=0;i<puddles.size();i++){ // 물에 잠긴곳 표시
        dp[puddles[i][1]-1][puddles[i][0]-1] = -1;
    }
    
    for(int i=0;i<n;i++){ // 초기화
        if(dp[0][i] == -1)
            break;
        dp[0][i] = 1;
    }
    for(int i=0;i<m;i++){
        if(dp[i][0] == -1)
            break;
        dp[i][0] = 1;
    }
    
    for(int i=1;i<m;i++){ // 경로 표시
        for(int j=1;j<n;j++){
            if(dp[i][j] == -1)
                continue;
            else{
                if(dp[i][j-1] != -1)
                    dp[i][j] += dp[i][j-1];
                if(dp[i-1][j] != -1)
                    dp[i][j] += dp[i-1][j];
                dp[i][j] = dp[i][j]%1000000007;
            }
        }
    }
    
    return dp[m-1][n-1];
}

模範解答

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int loc[m][n];

    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            loc[i][j] = 0;

    for (vector<int> p : puddles)
        loc[p[0]-1][p[1]-1] = -1;

    for (int i = 0; i < m; ++i)
    {
        if (loc[i][0] == -1)
            break;
        loc[i][0] = 1;
    }

    for (int i = 1; i < n; ++i)
    {
        if (loc[0][i] == -1)
            break;
        loc[0][i] = 1;
    }

    for (int i = 1; i < m; ++i)
        for (int j = 1; j < n; ++j)
        {
            if (loc[i][j])
                continue;

            if (loc[i-1][j] != -1)
                loc[i][j] += loc[i-1][j];
            if (loc[i][j-1] != -1)
                loc[i][j] += loc[i][j-1];

            loc[i][j] %= 1000000007;
        }

    return loc[m-1][n-1];
}

学ぶべきところ