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~.