Question

How to find a path from top-left to bottom right of a grid with a minimum sum of all numbers along the path in C++

Answer 1

#include <iostream>
#include <vector>
#include <climits>

// Minimum Path Sum
// We can only move down or right

void Print2DVector(std::vector<std::vector<int>> vec2d) {
    for (std::vector<int> vec1d : vec2d) {
        for (int val : vec1d) {
            std::cout << val << "  ";
        }    
        std::cout << "\n";
    }
}

int minPathSum(std::vector<std::vector<int>>& grid) {
    int rows = grid.size();
    int cols = grid[rows - 1].size();
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            int current = INT_MAX;
            if (i - 1 >= 0) {
                current = std::min(current, grid[i - 1][j]);
            }
            if (j - 1 >= 0) {
                current = std::min(current, grid[i][j - 1]);
            }
            if (current == INT_MAX) {
                current = 0;
            }
            grid[i][j] += current;
        }
    }
    
    Print2DVector(grid);
    
    return grid[rows - 1][cols - 1];
}
 
int main()
{
    std::vector<std::vector<int>> grid {
        { 1,2,3,1,4 },
        { 2,1,1,3,3 },
        { 3,2,2,1,5 },
        { 1,2,1,4,1 }
    };
     
    // [0][0] (1) + [0][1] (2) + [1][1] (1) + [1][2] (1) + 
    // [2][2] (2) + [2][3] (1) + [3][3] (4) + [3][4] (1) = 
    // 1 + 2 + 1 + 1 + 2 + 1 + 4 + 1 = 13
    
    std::cout << minPathSum(grid);
}
 


/*
run:
 
1  3  6  7  11  
3  4  5  8  11  
6  6  7  8  13  
7  8  8  12  13  
13
 
*/

 

70+ SQL courses for beginners and professionals