Участник:Михеева Анастасия Максимовна/Number of Paths with Max Score — различия между версиями

Версия 15:54, 25 мая 2020

• https://leetcode.com/problems/number-of-paths-with-max-score

class Solution {
public:
    typedef long long ll;
    vector<int> pathsWithMaxScore(vector<string>& board)
    {
        int m=board.size();
        if(m==0)
            return{0,0};
        ll mod=1e9+7;
        int n=board[0].size();
        vector<vector<ll>> dpsum(m,vector<ll>(n)),dppath(m,vector<ll>(n));
        for(int i=n-2;i>=0;i--)
        {
            if(board[m-1][i]=='X')
                break;
            dpsum[m-1][i]+=dpsum[m-1][i+1]+board[m-1][i]-'0';
            dppath[m-1][i]=1;
        }
        for(int i=m-2;i>=0;i--)
        {
            if(board[i][n-1]=='X')
                break;
            dpsum[i][n-1]+=dpsum[i+1][n-1]+board[i][n-1]-'0';
            dppath[i][n-1]=1;
        }
 
        for(int i=m-2;i>=0;i--)
        {
            for(int j=n-2;j>=0;j--)
            {
                if(board[i][j]=='X')
                    continue;
                ll maxm=max(dpsum[i+1][j],max(dpsum[i+1][j+1],dpsum[i][j+1]));
                    if(maxm==0)
                    {
                        if(i==m-2 && j==n-2)
                            dppath[i][j]=1,dpsum[i][j]=(board[i][j]=='E')?0:board[i][j]-'0';
                        continue;
                    }
                else dpsum[i][j]=(maxm+(board[i][j]-'0'))%mod;
                if(i==0 && j==0)
                    dpsum[i][j]=maxm%mod;
                if(dpsum[i][j+1]==maxm)
                    dppath[i][j]=(dppath[i][j]+dppath[i][j+1])%mod;
                if(dpsum[i+1][j+1]==maxm)
                    dppath[i][j]=(dppath[i][j]+dppath[i+1][j+1])%mod;
                if(dpsum[i+1][j]==maxm)
                    dppath[i][j]=(dppath[i][j]+dppath[i+1][j])%mod;
            }
        }
        return {(int)dpsum[0][0],(int)dppath[0][0]};
    }
};