Peanut Harvesting Problem

Problem Description

Traverse an R x C grid of peanut plants starting at the top-left corner and exiting at the bottom-right corner. Each cell holds a non-negative integer representing the number of peanuts available at that location. You may only move right or downward at any step, and collect all peanuts from every cell you pass through. Compute the maximum number of peanuts you can collect across all valid paths.

Input Format

• First line: Integer T, the number of independent test cases
• For each test case:
  • First line: Two integers R (row count) and C (column count)
  • Next R lines: Each contains C integers, representing peanut counts for cells in the row from left to right

Output Format

For each test case, output a single integer indicating the maximum collectible peanuts.

Constraints

1 ≤ T ≤ 100, 1 ≤ R, C ≤ 100, 0 ≤ peanut count per cell ≤ 1000

Sample Input

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

Sample Output

8
16

Solution Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        int rows, cols;
        cin >> rows >> cols;
        vector<vector<int>> grid(rows + 1, vector<int>(cols + 1, 0));
        vector<vector<int>> max_harvest(rows + 1, vector<int>(cols + 1, 0));
        for (int i = 1; i <= rows; ++i) {
            for (int j = 1; j <= cols; ++j) {
                cin >> grid[i][j];
            }
        }
        for (int i = 1; i <= rows; ++i) {
            for (int j = 1; j <= cols; ++j) {
                max_harvest[i][j] = max(max_harvest[i-1][j], max_harvest[i][j-1]) + grid[i][j];
            }
        }
        cout << max_harvest[rows][cols] << '\n';
    }
    return 0;
}

Minimum Grid Traversal Cost

Problem Description

Traverse a N x N square grid starting at the top-left entry point and exiting at the bottom-right corner. Each cell has a fixed traversal cost, and you must complete the traversal in exactly 2N - 1 steps (the minimum possible, meaning you can only move right or downward, no detours allowed). Calculate the minimum total cost to complete the traversal.

Input Format

• First line: Integer N, the side lengtth of the square grid
• Next N lines: Each contains N integers representing the traversal cost of the corresponding cell in the row

Output Format

Output a single integer indicating the minimum total traversal cost.

Constraints

1 ≤ N ≤ 100, 0 ≤ cell traversal cost ≤ 100

Sample Input

5
1  4  6  8  10 
2  5  7  15 17 
6  8  9  18 20 
10 11 12 19 21 
20 23 25 29 33

Sample Output

109

Sample Explanation

The minimum cost path sum is 109 = 1 + 2 + 5 + 7 + 9 + 12 + 19 + 21 + 33.

Solution Code

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int grid_size;
    cin >> grid_size;
    vector<vector<int>> cost_grid(grid_size + 1, vector<int>(grid_size + 1));
    vector<vector<int>> min_traversal_cost(grid_size + 1, vector<int>(grid_size + 1, INT_MAX));
    
    for (int i = 1; i <= grid_size; ++i) {
        for (int j = 1; j <= grid_size; ++j) {
            cin >> cost_grid[i][j];
        }
    }
    
    min_traversal_cost[1][1] = cost_grid[1][1];
    for (int i = 1; i <= grid_size; ++i) {
        for (int j = 1; j <= grid_size; ++j) {
            if (i > 1) {
                min_traversal_cost[i][j] = min(min_traversal_cost[i][j], min_traversal_cost[i-1][j] + cost_grid[i][j]);
            }
            if (j > 1) {
                min_traversal_cost[i][j] = min(min_traversal_cost[i][j], min_traversal_cost[i][j-1] + cost_grid[i][j]);
            }
        }
    }
    
    cout << min_traversal_cost[grid_size][grid_size] << '\n';
    return 0;
}