3584 - [CCC 2024 J5] 收获滑铁卢

题目描述

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

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

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

输入

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

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

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

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

输出

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

样例

输入

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解释

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

矩阵的具体分布图如下所示,农民的可活动范围为黄色区域。

农民在第 2 行第 4 列开始可以收割 19 个南瓜。可以收割到 8 个小南瓜,6 个中等大小的南瓜和 5 个大南瓜。收割的南瓜的总价值是 8 \times 1 + 6 \times 5 + 5 \times 10 = 88

数据范围

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

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

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题