Problem J45: Weed Removal / 清除杂草

版权信息： · 模拟移动与状态转换问题

---

任务总览

任务名称	时间限制	内存限制	分数
清除杂草	1 sec	1024 MB	15 points

---

题目描述

有一块 $n \times m$ 的土地，其中：

• "W" 表示该地块长满杂草；
• "G" 表示该地块为空地。

一位除草人站在 $(1,1)$ 位置，初始面朝方向为右（即朝向 $(1, m)$ 方向）。 他可以进行如下两种操作，每次操作耗费 1 单位时间：

1. 向当前面朝的方向移动一格；
2. 向下移动一格，并​反转面朝方向​（右变左，左变右）。

目标是​**清除所有的杂草（W）​，即访问所有杂草格子。求完成这一目标所需的最小单位时间。完成后不需要返回起点。

---

输入格式

• 第一行包含两个整数 $n$ 和 $m$；
• 接下来 $n$ 行，每行一个长度为 $m$ 的字符串，仅包含字符 G 或 W，表示土地状态。

约束条件： $1 \leq n, m < 150$

---

输出格式

输出一个整数，表示清除所有杂草所需的最小单位时间。

---

输入输出样例

输入示例

4 5
GWGGW
GGWGG
GWGGG
WGGGG

输出示例

11

---

题目分析与解法

✅ 解法思路：

• 将整块土地视为一个矩阵，从上到下按行处理；
• 每当当前行存在 "W"，必须遍历到最远的 "W" 所在列；
• 假设当前面朝方向为 →，则从左到右依次遍历；
• 如果下一行有 "W"，则必须向下走一格并反转方向；
• 若当前行没有 "W"，可以直接向下移动但仍需花费 1 单位时间。

🧠 动作模拟：

1. 设 cur_row = 0, cur_col = 0, dir = +1；
2. 从上到下模拟每一行的移动与方向；
3. 每次尽可能以最短路径扫完当前行的杂草，再决定是否向下反转。

---

边界细节说明

• 如果某一行没有杂草，不需要横向移动；
• 如果整张地无杂草，输出为 0；
• 清除所有 W 后即可结束，无需返回起点。

---

时间复杂度分析

操作	复杂度
每行遍历最远W	$O(m)$
模拟总过程	$O(n \cdot m)$

---