#P10294. [CCC 2024 J5] Harvest Waterloo【必做】

[CCC 2024 J5] Harvest Waterloo【必做】

题目描述

有一款新出现的广受欢迎的收割模拟游戏叫做 Harvest Waterloo。游戏在一块矩形南瓜地上进行,南瓜地里有成捆的干草和不同大小的南瓜。游戏开始时,一个农民在其中一个南瓜的位置上。

农民通过在整片土地上向左、向右、向上或向下移动来收割南瓜。农民不能斜着移动,不能穿过干草,也不能离开田地。

你的工作是确定农民收获的南瓜的总价值。其中一个小南瓜值 11 美元,一个中等大小的南瓜值 55 美元,而一个大南瓜值 1010 美元。

输入格式

输入的第一行是一个整数 R>0R > 0 表示南瓜地的行数。

第二行是一个整数 C>0C > 0 表示南瓜地的列数。

接下来 RR 行描述了整个南瓜地。每行包含 CC 个字符并且每个字符要么表示一个南瓜,要么表示干草:S 表示小南瓜,M 表示中等大小的南瓜,L 表示一个大南瓜,* 表示干草。

下一行包含一个整数 AA 满足 0A<R0 \leq A < R,最后一行是一个整数 BB 满足 0B<C0 \leq B < C。表示农民一开始在第 AA 行第 BB 列的位置。南瓜地的左上角称为第 00 行第 00 列。

输出格式

输出一个整数 VV 表示农民能够收割的南瓜的总价值。

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

37

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

88

提示

【样例 1 解释】

农民在第 55 行第 11 列开始可以收割 66 个南瓜。可以收割到 22 个小南瓜,11 个中等大小的南瓜和 33 个大南瓜。收割的南瓜的总价值是 2×1+1×5+3×10=372 \times 1 + 1 \times 5 + 3 \times 10 = 37

【样例 2 解释】

农民在第 22 行第 44 列开始可以收割 1919 个南瓜。可以收割到 88 个小南瓜,66 个中等大小的南瓜和 55 个大南瓜。收割的南瓜的总价值是 8×1+6×5+5×10=888 \times 1 + 6 \times 5 + 5 \times 10 = 88

【数据范围】

本题采用捆绑测试。

对于所有数据,保证 1R,C1051\leq R,C\leq 10^51R×C1051\leq R\times C\leq 10^5

下面的表格显示了 1515 分的分配方案:

分值 描述 范围
11 南瓜地很小并且不存在干草。 R×C100R \times C \leq 100
44 南瓜地很小并且干草把南瓜地分割为一些矩形区域。
55 南瓜地很小并且干草可以在任意位置。
南瓜地可能很大并且干草可以在任意位置。 R×C105R \times C \leq 10^5