c++ - Minimum Path Sum -


i'm working on algorithm problem have find minimum path sum of grid can move up, down, left, or right, , cannot repeat square. wrote recursive solution solve (i know dp better), outputs 0 answer every time, finds minimum sum 215 (should 87). how fix code solve it?

also, how use dp implement this?

here code:

#include<fstream> #include<iostream> #include<algorithm>  int rows; int cols; /*  * assumes max grid size 1000x1000  * go larger if necessary, memory use 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;     (int = 0; < rows; i++)         (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; } 

probably this:

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

Comments

Popular posts from this blog

resizing Telegram inline keyboard -

command line - How can a Python program background itself? -

php - "cURL error 28: Resolving timed out" on Wordpress on Azure App Service on Linux -