Robot coin collection - Dynamic Programming

Question

Robot Coin Collecting Problem

Several coins are placed in cells of an n × m board, no more than one coin per cell. A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell. On each step, the robot can move either one cell to the right or one cell down from its current location. When the robot visits a cell with a coin, it always picks up that coin. Design an algorithm to find the maximum number of coins the robot can collect and a path it needs to follow to do this.

How would you modify the dynamic programming algorithm for the coin- collecting problem if some cells on the board are inaccessible for the robot? Apply your algorithm to the board below, where the inaccessible cells are shown by X’s. How many optimal paths are there for this board?

I coded for the above image, and it works well as the output shows 4. The inaccessible cell is marked as -1. However, I made a[0][1]=1 accessible and I got a weird problem which shows a[1][0]=3 after initialisation and the output is 6 instead of 5. How is the cell a[1][0] showing as 3 instead of being 1? Whatever I change at a[0][1] is getting affected at a[1][0]. How is that? Where am I going wrong?

#include <stdio.h>

int max(int a,int b) 
{
    return a>b?a:b;
}

int robot_coin_collect(int m,int n,int a[][n])
{
    int i=1,j=1,k,c[m][n];

    c[0][0]=a[0][0];
    while(a[i][0]!=-1)
    {
        c[i][0]=c[i-1][0]+a[i][0];
        i=i+1;
    }
    for(;i<m;i++)
        c[i][0]=-6;
    while(a[0][j]!=-1)
    {
        c[0][j]=c[0][j-1]+a[0][j];
        j=j+1;
    }
    for(;j<n;j++)
        c[0][j]=-6;

    display(m,n,c);      // after initialising 
    printf("\n\n");

    for(i=1;i<m;i++)
    {
         for(j=1;j<n;j++)
         {
            if(a[i][j]!=-1)
                c[i][j]=max(c[i-1][j],c[i][j-1])+a[i][j];
            else
                c[i][j]=-6;
         }
    } 

    display(m,n,c);      // after the algorithm finishes, result
    return c[m-1][n-1];
}

void display(int m,int n,int c[][n])
{
     int i,j;

     for(i=0;i<m;i++)  
     {   
        for(j=0;j<n;j++)
            printf("%d\t",c[i][j]);
        printf("\n");
    }
}

int main(void) 
{
     int a[5][6]={0,1,0,1,0,0,
                 1,0,0,-1,1,0,
                 0,1,0,-1,1,0,
                 0,0,0,1,0,1,
                 -1,-1,-1,0,1,0};

     printf("%d",robot_coin_collect(5,6,a));
     return 0;
}

while(a[0][j]!=-1) { c[0][j]=c[0][j-1]+a[0][j]; j=j+1; } a[0][1] is not -1 when you made it accessible, add limit bound condition — Mojtaba Khooryani, Jul 24 '16 at 17:26
limit bound condition? like what? I mean why is `a[1][0]` varying, for values that are changed at `a[0][1]`? — sagar_jeevan, Jul 24 '16 at 17:29
limit bound worked. Thanks for the solution. But I don't understand how that really affected the cell `a[1][0]`. — sagar_jeevan, Jul 24 '16 at 18:08

score 3 · Accepted Answer · edited May 23 '17 at 10:31

3

problem is your code can modify the cell of memory which is out of the array bounds when there isn't any -1 in the first row or first column

this is strange why there is no runtime error, you can see this link and this

add bound limit in while condition:

while(i<m && a[i][0]!=-1)
{
    c[i][0]=c[i-1][0]+a[i][0];
    i=i+1;
}

and

while(j<n && a[0][j]!=-1)
{
    c[0][j]=c[0][j-1]+a[0][j];
    j=j+1;
}

edited May 23 '17 at 10:31

Community

1
1

answered Jul 24 '16 at 19:14

Mojtaba Khooryani

1,763
1
17
36

Totally get that. Just because arrays are contiguous memory blocks, after `j` exceeds the array bounds of `a[0][j]`, the array positions at `a[1][j]` got affected until it encountered `a[1][j]!=-1` at position `j=3`. The link helped and thanks for the detailed solution. – sagar_jeevan Jul 24 '16 at 19:32
1

not always, depends on OS memory management to give which address to the process. I edited answer a bit check it, good luck. – Mojtaba Khooryani Jul 24 '16 at 19:38

score 0 · Answer 2 · edited May 18 '17 at 07:48

int CoinCollecting(int c[][], int M[][],int i,int j){
    int Max(int a,int b) 
    {
        return a>b?a:b;
    }
    if(i==0 || j==0)
    {
        M[i][j]=0;
        return 0;
    }
    if(m[i-1][j]<0)
    {
        M[i-1][j]=CoinCollecting(c[][],M[][],i-1,j);
    }

if(m[i][j-1]<0)
{
    M[i][j-1]=CoinCollecting(c[][],M[][],i,j-1);
}

M[i][j]=Max(M[i-1][j],M[i][j-1]+c[i][j]);
return M[i][j]
}

Robot coin collection - Dynamic Programming

2 Answers2