CPP Soln.. Question asks whether we can reach the bottom row or not. If possible return the length of the longest path


#1
int Solution::solve(vector<vector<int> > &a) {
    if(a.empty()) return 0;
    int m = a.size(), n = a[0].size();
    vector<vector<int>> dp(m,vector<int>(n,0));
    for(int i=m-1; i>=0; i--)
    {
        for(int j=n-1; j>=0; j--)
        {
            if(i==m-1 && j == n-1)
            {
                dp[i][j] = 1;
            }
            else if(i == m-1)
            {
                if(a[i][j] < a[i][j+1]) dp[i][j] = 1 + dp[i][j+1];
            }
            else if(j == n-1)
            {
                if(a[i][j] < a[i+1][j]) dp[i][j] = 1 + dp[i+1][j];
            }
            else
            {
                int x1=INT_MIN,x2=INT_MIN;
                if(a[i+1][j] > a[i][j]) x1 = dp[i+1][j]+1;
                if(a[i][j+1] > a[i][j]) x2 = dp[i][j+1]+1;
                dp[i][j] = max({dp[i][j],x1,x2});
            }
        }
    }
    
    return dp[0][0] < n-1 ? -1 : dp[0][0];
}