题目描述

难度分:$1500$

输入$n$、$m(1 \leq n,m \leq 150)$和$n$行$m$列的网格图，每个格子要么是 G，要么是W。

W表示杂草。你推着割草机，从左上角出发，目标是清除所有的杂草。一开始你面朝右边。你可以：

1. 如果你面朝右边，那么可以往右移动一步。
2. 如果你面朝左边，那么可以往左移动一步。
3. 往下移动一步，并改变朝向。

清除所有的杂草，最少需要移动多少步？

输入样例$1$

4 5
GWGGW
GGWGG
GWGGG
WGGGG

输出样例$1$

11

输入样例$2$

3 3
GWW
WWW
WWG

输出样例$2$

7

输入样例$3$

1 1
G

输出样例$3$

0

算法

贪心

这个题也没什么算法，主要就是根据直觉来贪心，分析几个$case$就能得到贪心策略。假设当前位置是$(x,y)$，分为以下两种情况讨论：

1. 如果当前朝向的方向还有没割掉的杂草，肯定是要往朝向走一步。
2. 否则先找到下面最近有杂草的行$r$，假设当前是朝右。如果行$r$和$x$的奇偶性相同，那么到达行$r$时朝向是不变的，直接往下走一格改变朝向，到下一行去做决策。如果行$r$和行$x$的奇偶性不同，那么到达行$r$时的朝向就会往左，此时为了把行$r$右边的杂草割掉，就需要根据第$r$行最后一块杂草所在列$right[r]$与$y$的关系来判断在当前行$x$是否还要往前走，当$right[r] \gt r$时，在当前行还需要往右走，直到到达第$right[r]$列（$right[r]$表示第$r$行最后一块杂草的列号）才停止往右，这样在往下走到行$r$时才能确保朝左能够割完第$r$行所有的杂草。否则也是向下走一步，到下一行去做决策。同理分析当前朝向往左的情况即可，还需要一个数组$left$，$left[r]$表示第$r$行第一块杂草的列号。

复杂度分析

时间复杂度

当处于位置$(x,y)$时，如果朝向的前方还有W，$O(1)$就能决定继续往前走。但是如果朝向的前方已经全是G时，就要往下找到最近那个有杂草的行再做判断，时间复杂度是$O(n)$。而模拟除草过程需要走$O(nm)$步，因此整体的时间复杂度为$O(n^2m)$。

空间复杂度

需要预处理出行$i \in [1,n]$第一块杂草的列$left[i]$，和最后一块杂草的列$right[i]$，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 160;
int n, m;
char grid[N][N];

int main() {
    scanf("%d%d", &n, &m);
    int rest = 0;
    int left[n + 1], right[n + 1] = {0};
    for(int i = 1; i <= n; i++) {
        scanf("%s", grid[i] + 1);
        left[i] = m + 1;
        for(int j = 1; j <= m; j++) {
            if(grid[i][j] == 'W') {
                rest++;
                if(left[i] == m + 1) left[i] = j;
                right[i] = j;
            }
        }
    }
    int x = 1, y = 1, step = 0;
    bool is_right = true;
    while(rest > 0) {
        if(grid[x][y] == 'W') rest--;
        if(is_right) {
            if(right[x] > y) {
                y++;
            }else {
                int r = x + 1;
                while(r <= n && right[r] == 0) {
                    r++;
                }
                if(r > n) break;
                if((x&1) == (r&1)) {
                    // 奇偶性相同，从x行到r行时还是朝右
                    x++;
                    is_right = false;
                }else {
                    // 奇偶性不同，从x行到r行会朝左
                    if(right[r] > y) {
                        y++;
                    }else {
                        x++;
                        is_right = false;
                    }
                }
            }
        }else {
            if(left[x] < y) {
                y--;
            }else {
                int r = x + 1;
                while(r <= n && right[r] == 0) {
                    r++;
                }
                if(r > n) break;
                if((x&1) == (r&1)) {
                    // 奇偶性相同，从x行到r行时还是朝左
                    x++;
                    is_right = true;
                }else {
                    // 奇偶性不同，从x行到r行会朝右
                    if(y > left[r]) {
                        y--;
                    }else {
                        x++;
                        is_right = true;
                    }
                }
            }
        }
        step++;
    }
    printf("%d\n", step);
    return 0;
}