CCC '24 J5 - Harvest Waterloo - Olympiads Online Judge

CCC '24 J5 - Harvest Waterloo

Points: 7 (partial)

Time limit: 3.0s

Memory limit: 1G

Problem types

Canadian Computing Competition: 2024 Stage 1, Junior #5

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$ $$ 1$ , a medium pumpkin is worth $\$5$ $$ 5$ , and a large pumpkin is worth $\$10$ $$ 10$ dollars.

Input Specification

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

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

The next $R$ $R$ lines describe the patch. Each line will contain $C$ $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$ $A$ where $0 \le A < R$ $0 \leq A < R$ , and the last line of input is an integer $B$ $B$ where $0 \le B < C$ $0 \leq B < C$ . Row $A$ $A$ and column $B$ $B$ is the starting location of the farmer and the top-left corner of the patch is row $0$ $0$ and column $0$ $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 \le 100$ $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 \le 100$ $R \times C \leq 100$
5	The patch is small and the bales of hay can be anywhere.	$R \times C \le 100$ $R \times C \leq 100$
5	The patch is large and the bales of hay can be anywhere.	$R \times C \le 100 \,000$ $R \times C \leq 100 000$

Output Specification

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

Sample Input 1

Copy

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

Output for Sample Input 1

Copy

Explanation of Output for Sample Input 1

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

Sample Input 2

Copy

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

Output for Sample Input 2

Copy

Explanation of Output for Sample Input 2

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

Comments

0

dhruvkangaroo commented 46 days ago

remember if ur using python to not forget about sys.setrecursionlimit(x) you will get IR error if u dont

0

Have_A_Nice_Life commented 44 days ago

or use bfs

0

ZakichanDraws commented 45 days ago

how big do you have to set it

0

bowen_wu commented 34 days ago

set it to 10^5 because the worst case is no haybales and r*c = 100000, in which case does 10^5 recursions. (note: maybe set it to 10^5 + 3 to prevent RecursionError because it works for me)

-2

dhruvkangaroo commented 40 days ago

just set it to a gigantic number till it doesn't give one. sys.setrecursionlimit(10^7)

3

iwantbred commented 57 days ago

happy early birthday