P10294 [CCC 2024 J5] Harvest Waterloo

A new and popular harvesting simulation game called Harvest Waterloo has appeared. The game is played on a rectangular pumpkin field. In the field, there are bundles of hay and pumpkins of different sizes. At the start of the game, a farmer is standing on the position of one of the pumpkins. The farmer harvests pumpkins by moving across the field left, right, up, or down. The farmer cannot move diagonally, cannot pass through hay, and cannot leave the field. Your task is to determine the total value of the pumpkins the farmer can harvest. A small pumpkin is worth $1$ dollar, a medium pumpkin is worth $5$ dollars, and a large pumpkin is worth $10$ dollars.

The first line of input is an integer $R > 0$, the number of rows in the pumpkin field. The second line is an integer $C > 0$, the number of columns in the pumpkin field. The next $R$ lines describe the entire pumpkin field. Each line contains $C$ characters, and each character represents either a pumpkin or hay: `S` represents a small pumpkin, `M` represents a medium pumpkin, `L` represents a large pumpkin, and `*` represents hay. The next line contains an integer $A$ satisfying $0 \leq A < R$, and the last line is an integer $B$ satisfying $0 \leq B < C$, indicating that the farmer starts at row $A$, column $B$. The top-left corner of the pumpkin field is called row $0$, column $0$.

Output an integer $V$, the total value of the pumpkins that the farmer can harvest.

**[Sample 1 Explanation]**  Starting at row $5$, column $1$, the farmer can harvest $6$ pumpkins. The farmer can harvest $2$ small pumpkins, $1$ medium pumpkin, and $3$ large pumpkins. The total value of the harvested pumpkins is $2 \times 1 + 1 \times 5 + 3 \times 10 = 37$. **[Sample 2 Explanation]**  Starting at row $2$, column $4$, the farmer can harvest $19$ pumpkins. The farmer can harvest $8$ small pumpkins, $6$ medium pumpkins, and $5$ large pumpkins. The total value of the harvested pumpkins is $8 \times 1 + 6 \times 5 + 5 \times 10 = 88$. **[Constraints]** **This problem uses bundled testdata.** For all testdata, it is guaranteed that $1 \leq R, C \leq 10^5$ and $1 \leq R \times C \leq 10^5$. The table below shows the $15$-point distribution: | Points | Description | Range | | :-: | :- | :-: | | $1$ | The pumpkin field is small and there is no hay. | $R \times C \leq 100$ | | $4$ | The pumpkin field is small and hay splits the field into some rectangular regions. | $R \times C \leq 100$ | | $5$ | The pumpkin field is small and hay can be anywhere. | $R \times C \leq 100$ | | $5$ | The pumpkin field may be large and hay can be anywhere. | $R \times C \leq 10^5$ | Translated by ChatGPT 5