j5 — CCO Canadian_Computing_Competition_Junior
Task type: batch | Time limit: 3 s | Memory limit: 512 MB | Difficulty: 9
Algorithms: graph traversal, bfs, graph theory, dfs

# Problem J5: Harvest Waterloo

### Problem Description

There is a wildly popular new harvest simulation game called Harvest Waterloo. The game is played on a rectangular pumpkin patch which contains bales of hay and pumpkins of different sizes. To begin the game, a farmer is placed at the location of a pumpkin.

The farmer harvests all pumpkins they can reach by moving left, right, up, and down throughout the patch. The farmer cannot move diagonally. The farmer can also not move through a bale of hay nor move outside of the patch.

Your job is to determine the total value of all the pumpkins harvested by the farmer. A small pumpkin is worth $1, a medium pumpkin is worth $5, and a large pumpkin is worth $10 dollars.

### Input Specification

The first line of input is an integer R > 0 which is the number of rows within the patch.

The second line of input is an integer C > 0 which is the number of columns within the patch.

The next R lines describe the patch. Each line will contain C characters and each character will either represent a pumpkin size or a bale of hay: S for a small pumpkin, M for a medium pumpkin, L for a large pumpkin, or * for a bale of hay.

The next line of input is an integer A where 0 ≤ A < R, and the last line of input is an integer B where 0 ≤ B < C. Row A and column B is the starting location of the farmer and the top-left corner of the patch is row 0 and column 0.

The following table shows how the available 15 marks are distributed:

| Marks | Description                                                                               | Bound                     |
|-------|-------------------------------------------------------------------------------------------|---------------------------|
| 1     | The patch is small and there are no bales of hay.                                         | $R \times C \leq 100$     |
| 4     | The patch is small and the bales of hay divide the entire patch into rectangular areas.  | $R \times C \leq 100$     |
| 5     | The patch is small and the bales of hay can be anywhere.                                 | $R \times C \leq 100$     |
| 5     | The patch is large and the bales of hay can be anywhere.                                 | $R \times C \leq 100 000$ |

### Output Specification

Output the integer, V, which is the total value in dollars of all the pumpkins harvested by the farmer.

La version française figure à la suite de la version anglaise.

### Sample Input 1

```
6
6
**LMLS
S*LMMS
S*SMSM
******
LLM*MS
SSL*SS
5
1
```

![](_page_1_Picture_1.jpeg)

### Output for Sample Input 1

```
37
```

### Explanation of Output for Sample Input 1

Starting at row 5 and column 1, the farmer can reach the 6 pumpkins in the highlighted area. They harvest 2 small pumpkins, 1 medium pumpkin, and 3 large pumpkins. The total value in dollars of this harvest is 2 × 1 + 1 × 5 + 3 × 10 = 37.

### Sample Input 2

```
6
6
**LMLS
S*LMMS
S*SMSM
***SLL
LLM*MS
SSL*SS
2
4
```

### Output for Sample Input 2

```
88
```

### Explanation of Output for Sample Input 2

Starting at row 2 and column 4, the farmer can reach the 19 pumpkins in the highlighted area. They harvest 8 small pumpkins, 6 medium pumpkin, and 5 large pumpkins. The total value in dollars of this harvest is 8 × 1 + 6 × 5 + 5 × 10 = 88.

La version française figure à la suite de la version anglaise.

Starter code: