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;
}

Solution

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;
}