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 <stdio.h>
#include <limits.h>

#define ROWS 4
#define COLS 5

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

void print2DArray(int grid[ROWS][COLS]) {
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            printf("%d  ", grid[i][j]);
        }
        printf("\n");
    }
}

int minPathSum(int grid[ROWS][COLS]) {
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            int current = INT_MAX;
            if (i - 1 >= 0) {
                if (grid[i - 1][j] < current) current = grid[i - 1][j];
            }
            if (j - 1 >= 0) {
                if (grid[i][j - 1] < current) current = grid[i][j - 1];
            }
            if (current == INT_MAX) {
                current = 0;
            }
            grid[i][j] += current;
        }
    }

    print2DArray(grid);
    
    return grid[ROWS - 1][COLS - 1];
}

int main() {
    int grid[ROWS][COLS] = {
        { 1, 2, 3, 1, 4 },
        { 2, 1, 1, 3, 3 },
        { 3, 2, 2, 1, 5 },
        { 1, 2, 1, 4, 1 }
    };

    int result = minPathSum(grid);
    printf("Minimum Path Sum: %d\n", result);

    return 0;
}



/*
run:

1  3  6  7  11  
3  4  5  8  11  
6  6  7  8  13  
7  8  8  12  13  
Minimum Path Sum: 13

*/

 

70+ SQL courses for beginners and professionals