Robot - Динамическое программирование

Question

Робот Сбор монет Проблема

Несколько монет размещены в ячейках с n × m платы, не более чем одна монета в клетку. Робот, расположенный в верхней левой ячейке платы , должен собрать как можно больше монет и принести их в нижнюю правую ячейку. На каждом шаге робот может перемещать либо одну ячейку вправо, либо одну ячейку вниз от ее текущего местоположения. Когда робот посещает ячейку с монетой, она всегда подбирает эту монету. Создайте алгоритм, чтобы найти максимальное количество монет, которое может собрать робот , и путь, которым он должен следовать, чтобы сделать это.

Как бы вы изменяли алгоритм динамического программирования для проблемы сбора монет, если некоторые ячейки на плате недоступны для робота ? Примените свой алгоритм к доске ниже, где недоступные ячейки показаны X. Сколько оптимальных путей для этой платы ?

Я кодируюсь на изображение выше, и она работает хорошо, как выход показывает 4. недоступной ячейка помечается как -1. Тем не менее, я сделал a[0][1]=1 доступным, и у меня возникла странная проблема, которая показывает a[1][0]=3 после инициализации, а выход 6 вместо 5. Как ячейка a[1][0] отображается как 3 вместо 1? Независимо от того, что я изменяю на a[0][1], на него влияет a[1][0]. Как так? Где я иду не так?

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

Answer 1

Проблема в том, что ваш код может изменить ячейку памяти, которая находится вне границ массива, когда нет каких-либо -1 в первой строке или первом столбце

это не странно, почему нет ошибка времени выполнения, вы можете увидеть this link и this

добавить связанный предел в то время как условие:

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

и

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

Answer 2

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