最小パスの総数

Question

私は、上、下、左、または右に移動できるグリッドの最小パスの合計を見つける必要があり、四角形を繰り返すことはできません。私はそれを解決するための再帰的な解決策を書いた（私はDPが良いだろうと知っている）が、毎回答えとして0を出力しますが、最小合計は215でなければなりません（87でなければなりません）。どのように私はそれを解決するコードを修正するだろうか？

また、DPを使用してこれを実装するにはどうすればよいですか？ここで

は私のコードです：

#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

おそらくこのような何か：

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