# Участник:Михеева Анастасия Максимовна/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]};
}
};