CareerCup

I believe it can be solved using dynamic programming.

First of all, starting from (0,0) and reaching the last cell, using right and down movements only, and then coming back using left and up movements only is same as starting from (0,0) and reaching last cell twice.

In first iteration we will start from 0,0 and reach last cell while collecting the diamonds
in second iteration, we will use the modified matrix (in which the diamonds have been collected on the path followed in the first step) and again use the same algorithm to find max-diamond-path.

To find optimal path in an iteration, we will use the following logic to build the matrix
- For first row, only left moves can reach a cell. Simply add the diamonds before a cell till a -1 is encountered
- For first column, only down moves can reach a cell. Add the diamonds before a cell till -1 is encountered
- For all other cells, either it can be reached from the cell above it or cell to the left of it. Depending on which cell has a higher diamond count, take that path

Here is my code for the solution described above: www[DOT]edufyme[DOT]com/code/?id=c20ad4d76fe97759aa27a0c99bff6710

what is the output required? total diamonds or path also?

/*
Given a matrix of n*n. Each cell contain 0, 1, -1. 
0 denotes there is no diamond but there is a path. 
1 denotes there is diamond at that location with a path 
-1 denotes that the path is blocked. 
Now you have start from 0,0 and reach to last cell & then return back to 0,0 collecting maximum no of diamonds. 
While going to last cell you can move only right and down. 
While returning back you can move only left and up.
*/
#include<bits/stdc++.h>
using namespace std;
long long n,d[1000][1000],ans[1000][1000];
pair<long long,long long> prev[1000][1000];
void solve()
{
    long long i,j;
    if(d[0][0]!=-1)
    {
        ans[0][0]=d[0][0];
        prev[0][0]=make_pair(-1,-1);
    }
    for(i=1;i<n;i++)
    {
        if(d[0][i]==-1)
            break;
        ans[0][i]=ans[0][i-1]+d[0][i];
        prev[0][i]=make_pair(0,i-1);
    }
    while(i<n)
    {
        ans[0][i]=-1;
        i++;
    }
    for(i=1;i<n;i++)
    {
        if(d[i][0]==-1)
            break;
        ans[i][0]=ans[i-1][0]+d[i][0];
        prev[i][0]=make_pair(i-1,0);
    }
    while(i<n)
    {
        ans[i][0]=-1;
        i++;
    }
    for(i=1;i<n;i++)
    {
        for(j=1;j<n;j++)
        {
            if(d[i][j]==-1)
            {
                ans[i][j]=-1;
                continue;
            }
            if(ans[i-1][j]>ans[i][j-1])
            {
                ans[i][j]=ans[i-1][j]+d[i][j];
                prev[i][j]=make_pair(i-1,j);
            }
            else
            {
                ans[i][j]=ans[i][j-1]+d[i][j];
                prev[i][j]=make_pair(i,j-1);
            }
        }
    }
}
void update()
{
    long long i,j;
    pair<long long,long long> node;
    i=n-1;
    j=n-1;
    while(i!=-1&&j!=-1)
    {
        node=prev[i][j];
        d[i][j]=0;
        i=node.first;
        j=node.second;
    }
}
void init()
{
    long long i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            ans[i][j]=0;
        }
    }
}
int main()
{
    long long i,j,res;
    res=0LL;
    cin>>n;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cin>>d[i][j];
        }
    }
    solve();
    res=res+ans[n-1][n-1];
    update();
    init();
    solve();
    res=res+ans[n-1][n-1];
    cout<<"Max Path Diamonds : "<<res;
    return 0;
}

0 1 -1 1
1 0 -1 1
1 1 1 0
1 0 1 0

LeetCode 741. Cherry Pickup

I think the maximum number of collected diamonds can be the best two paths to reach the last cell. Probably, the following logic can work.

int fun(int mat[][N] ) {
		int table[N][N];
		table[0][0] = mat[0][0];
		for(int i=1;i<n;i++)	{
			if(mat[i][i] != -1)
				table[i][0] = table[i-1][0] + mat[i][0];
			else 
				table[i][0] = -1;
		}
		for(int j=1;j<n;j++)	{
			if(mat[[0][j] != -1)
				table[0][j] = table[0][j-1] + mat[0][j];
			else
				table[0][j] = -1;	
		}
		for(int i=1;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(mat[i][j] != -1)
					table[i][j] = max(table[i][j-1],table[i-1][j]) + mat[i][j];
				else
					table[i][j] = -1;
			}
		}
		if(table[n-1][n-2] < 0 || table[n-2][n-1] < 0) {
			cout<<"No Roundtrip path possible";
			return -1;
		}
		return table[n-2][n-1] + table[n-1][n-2] + mat[n-1][n-1] - mat[0][0];
	}