Problem: CCC 2024 Junior 5 – Harvest Waterloo

Core idea: This is a grid traversal problem. Starting from the farmer’s position, visit every pumpkin reachable by moving up, down, left, and right. Bales of hay block movement. Add the value of each reachable pumpkin.

Problem Summary

The pumpkin patch is an R x C grid. Each cell contains one of four characters:

• S: small pumpkin, worth 1 dollar
• M: medium pumpkin, worth 5 dollars
• L: large pumpkin, worth 10 dollars
• *: bale of hay, cannot be entered

The farmer starts at row A, column B. They can move only in the four cardinal directions. The task is to output the total value of all reachable pumpkins.

Thinking Process

The important observation is that the farmer can harvest exactly the connected component of pumpkin cells that contains the starting position. Hay cells split the grid into separate regions.

So we do not need a complicated simulation. We just need a standard flood fill:

1. Put the starting cell into a queue or stack.
2. Repeatedly take one cell out.
3. If it has not been visited, add its pumpkin value.
4. Try moving to its four neighbours.
5. Ignore neighbours that are outside the grid, already visited, or hay.

Why BFS/DFS Works

BFS and DFS both explore all cells reachable from the starting point. Since each valid cell is processed once, either approach gives the same total harvest value. BFS uses a queue; DFS can use a stack. In Python, an iterative BFS is a safe choice for large grids because it avoids recursion depth issues.

Python Solution

from collections import deque

R = int(input())
C = int(input())
grid = [input().strip() for _ in range(R)]
A = int(input())
B = int(input())

value = {
    "S": 1,
    "M": 5,
    "L": 10,
}

visited = [[False] * C for _ in range(R)]
queue = deque([(A, B)])
total = 0

while queue:
    r, c = queue.popleft()

    if r < 0 or r >= R or c < 0 or c >= C:
        continue
    if visited[r][c]:
        continue
    if grid[r][c] == "*":
        continue

    visited[r][c] = True
    total += value[grid[r][c]]

    queue.append((r + 1, c))
    queue.append((r - 1, c))
    queue.append((r, c + 1))
    queue.append((r, c - 1))

print(total)

C++ Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int R, C;
    cin >> R >> C;

    vector<string> grid(R);
    for (int i = 0; i < R; i++) {
        cin >> grid[i];
    }

    int A, B;
    cin >> A >> B;

    map<char, int> value;
    value['S'] = 1;
    value['M'] = 5;
    value['L'] = 10;

    vector<vector<bool>> visited(R, vector<bool>(C, false));
    queue<pair<int, int>> q;
    q.push({A, B});

    int total = 0;
    int dr[4] = {1, -1, 0, 0};
    int dc[4] = {0, 0, 1, -1};

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        if (r < 0 || r >= R || c < 0 || c >= C) continue;
        if (visited[r][c]) continue;
        if (grid[r][c] == '*') continue;

        visited[r][c] = true;
        total += value[grid[r][c]];

        for (int k = 0; k < 4; k++) {
            q.push({r + dr[k], c + dc[k]});
        }
    }

    cout << total << endl;
    return 0;
}

Complexity Analysis

Each grid cell is visited at most once. The time complexity is O(R x C), and the memory usage is also O(R x C) for the visited array and queue.

Common Mistakes

• Trying to move diagonally. Only four directions are allowed.
• Forgetting that hay cells * block movement.
• Marking cells visited too late and adding the same pumpkin more than once.
• Using recursive DFS in Python on a large grid and hitting recursion depth limits.
• Mixing up row and column order for the starting location.

Learning Outcomes

• Recognize a connected component problem in a grid.
• Use BFS or DFS to perform flood fill.
• Track visited cells to avoid repeated work.
• Translate problem characters into values using a dictionary or map.

Problem reference: CCC 2024 J5 – Harvest Waterloo on DMOJ