[CCC 2024 J5] Harvest Waterloo

Luogu

IDLGP10294

Time3000ms

Memory512MB

DifficultyP2

搜索2024CCC（加拿大）广度优先搜索 BFS深度优先搜索 DFS

有一款新出现的广受欢迎的收割模拟游戏叫做 Harvest Waterloo。游戏在一块矩形南瓜地上进行，南瓜地里有成捆的干草和不同大小的南瓜。游戏开始时，一个农民在其中一个南瓜的位置上。农民通过在整片土地上向左、向右、向上或向下移动来收割南瓜。农民不能斜着移动，不能穿过干草，也不能离开田地。你的工作是确定农民收获的南瓜的总价值。其中一个小南瓜值 $1$ 美元，一个中等大小的南瓜值 $5$ 美元，而一个大南瓜值 $10$ 美元。 ## Input 输入的第一行是一个整数 $R > 0$ 表示南瓜地的行数。第二行是一个整数 $C > 0$ 表示南瓜地的列数。接下来 $R$ 行描述了整个南瓜地。每行包含 $C$ 个字符并且每个字符要么表示一个南瓜，要么表示干草：`S` 表示小南瓜，`M` 表示中等大小的南瓜，`L` 表示一个大南瓜，`*` 表示干草。下一行包含一个整数 $A$ 满足 $0 \leq A < R$，最后一行是一个整数 $B$ 满足 $0 \leq B < C$。表示农民一开始在第 $A$ 行第 $B$ 列的位置。南瓜地的左上角称为第 $0$ 行第 $0$ 列。 ## Output 输出一个整数 $V$ 表示农民能够收割的南瓜的总价值。 [samples] ## Note **【样例 1 解释】** ![](https://cdn.luogu.com.cn/upload/image_hosting/sppn2crp.png) 农民在第 $5$ 行第 $1$ 列开始可以收割 $6$ 个南瓜。可以收割到 $2$ 个小南瓜，$1$ 个中等大小的南瓜和 $3$ 个大南瓜。收割的南瓜的总价值是 $2 \times 1 + 1 \times 5 + 3 \times 10 = 37$。 **【样例 2 解释】** ![](https://cdn.luogu.com.cn/upload/image_hosting/dni4nwdv.png) 农民在第 $2$ 行第 $4$ 列开始可以收割 $19$ 个南瓜。可以收割到 $8$ 个小南瓜，$6$ 个中等大小的南瓜和 $5$ 个大南瓜。收割的南瓜的总价值是 $8 \times 1 + 6 \times 5 + 5 \times 10 = 88$。 **【数据范围】** **本题采用捆绑测试。** 对于所有数据，保证 $1\leq R,C\leq 10^5$，$1\leq R\times C\leq 10^5$。下面的表格显示了 $15$ 分的分配方案： | 分值 | 描述 | 范围 | | :-: | :- | :-: | | $1$ | 南瓜地很小并且不存在干草。 | $R \times C \leq 100$ | | $4$ | 南瓜地很小并且干草把南瓜地分割为一些矩形区域。 | $R \times C \leq 100$ | | $5$ | 南瓜地很小并且干草可以在任意位置。 | $R \times C \leq 100$ | | $5$ | 南瓜地可能很大并且干草可以在任意位置。 | $R \times C \leq 10^5$ |

Samples

Input #1

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

Output #1

Input #2

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

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[CCC 2024 J5] Harvest Waterloo",
    "description": {
      "content": "有一款新出现的广受欢迎的收割模拟游戏叫做 Harvest Waterloo。游戏在一块矩形南瓜地上进行，南瓜地里有成捆的干草和不同大小的南瓜。游戏开始时，一个农民在其中一个南瓜的位置上。 农民通过在整片土地上向左、向右、向上或向下移动来收割南瓜。农民不能斜着移动，不能穿过干草，也不能离开田地。 你的工作是确定农民收获的南瓜的总价值。其中一个小南瓜值 $1$ 美元，一个中等大小的南瓜值 $5$ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10294"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一款新出现的广受欢迎的收割模拟游戏叫做 Harvest Waterloo。游戏在一块矩形南瓜地上进行，南瓜地里有成捆的干草和不同大小的南瓜。游戏开始时，一个农民在其中一个南瓜的位置上。\n\n农民通过在整片土地上向左、向右、向上或向下移动来收割南瓜。农民不能斜着移动，不能穿过干草，也不能离开田地。\n\n你的工作是确定农民收获的南瓜的总价值。其中一个小南瓜值 $1$ 美元，一个中等大小的南瓜值 $5$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments