Somme de chemin minimale

Question

Je travaille sur un problème d'algorithme où vous devez trouver la somme de chemin minimum d'une grille où vous pouvez monter, descendre, gauche ou droite, et vous ne pouvez pas répéter un carré. J'ai écrit une solution récursive pour la résoudre (je sais que le DP serait meilleur), mais elle renvoie 0 comme réponse à chaque fois, mais trouve la somme minimale à 215 (devrait être 87). Comment est-ce que je fixerais le code pour le résoudre?

En outre, comment pourrais-je utiliser DP pour implémenter cela?

Voici mon code:

#include<fstream> 
#include<iostream> 
#include<algorithm> 

int rows; 
int cols; 
/* 
* assumes max grid size is 1000x1000 
* could go larger if necessary, but memory use will increase 
*/ 
int grid[1000][1000]; 
bool isMarked[1000][1000]; 

int calc(int row, int col, int sum) { 
    if (isMarked[row][col]) 
     return INT_MAX - sum; 
    isMarked[row][col] = true; 
    sum += grid[row][col]; 
    if (row == rows-1 && col == cols-1) 
     return sum; 

    int ans[4]; 
    if (row-1 >= 0) 
     ans[0] = calc(row-1, col, sum); 
    if (row+1 < rows) 
     ans[1] = calc(row+1, col, sum); 
    if (col+1 < cols) 
     ans[2] = calc(row, col+1, sum); 
    if (col-1 >= 0) 
     ans[3] = calc(row, col-1, sum); 
    isMarked[row][col] = false; 
    return std::min(std::min(ans[0], ans[1]), std::min(ans[2], ans[3])); 
} 

int main() { 
    std::ifstream fin("sum.in"); 
    fin >> rows >> cols; 
    for (int i = 0; i < rows; i++) 
     for (int j = 0; j < cols; j++) 
      fin >> grid[i][j]; 

    int ans = calc(0, 0, 0); 

    std::ofstream fout("sum.out"); 
    fout << ans << std::endl; 
} 

Answer 1

Probablement quelque chose comme ceci:

int calc(int row, int col, int sum) { 
    if (isMarked[row][col]) 
     return INT32_MAX; 
    if (row == rows-1 && col == cols-1) 
     return sum+grid[row][col]; 

    isMarked[row][col] = true; 
    int ans[4] = {INT32_MAX, INT32_MAX, INT32_MAX, INT32_MAX}; 
    if (row-1 >= 0) 
     ans[0] = calc(row-1, col, sum+grid[row][col]); 
    if (row+1 < rows) 
     ans[1] = calc(row+1, col, sum+grid[row][col]); 
    if (col+1 < cols) 
     ans[2] = calc(row, col+1, sum+grid[row][col]); 
    if (col-1 >= 0) 
     ans[3] = calc(row, col-1, sum+grid[row][col]); 
    isMarked[row][col] = false; 

    return std::min(std::min(ans[0], ans[1]), std::min(ans[2], ans[3])); 
}