CCC '24 J5 - Harvest Waterloo

View as PDF
Submit solution
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, 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 \le A < R, and the last line of input is an integer B where 0 \le 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 \le 100
4 The patch is small and the bales of hay divide the entire patch into rectangular areas. R \times C \le 100
5 The patch is small and the bales of hay can be anywhere. R \times C \le 100
5 The patch is large and the bales of hay can be anywhere. R \times C \le 100 \,000

Output Specification

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

Sample Input 1

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

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 \times 1 + 1 \times 5 + 3 \times 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 \times 1 + 6 \times 5 + 5 \times 10 = 88.

Comments


  • 0
    kyleandjunyi  commented on Sept. 30, 2025, 1:03 a.m.

    HI


  • 1
    dhruvkangaroo  commented on Feb. 5, 2025, 11:47 p.m.

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


    • 1
      Have_A_Nice_Life  commented on Feb. 7, 2025, 2:56 p.m.

      or use bfs


    • 1
      ZakichanDraws  commented on Feb. 6, 2025, 6:01 p.m.

      how big do you have to set it


      • 2
        bowen_wu  commented on Feb. 17, 2025, 12:50 p.m.

        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)


      • -7
        dhruvkangaroo  commented on Feb. 11, 2025, 3:25 p.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


  • 6
    iwantbred  commented on Jan. 25, 2025, 7:04 p.m.

    happy early birthday