← 返回题目列表

Codeforces · 115/B

B. 割草机

中文机器翻译题面 查看原题

你有一个完全由草和杂草组成的花园。您的花园由 n × m 网格描述,从上到下,行编号为 1 到 n,从左到右编号为 1 到 m 列。每个单元格由一对 (r, c) 标识,这意味着该单元格位于 r 行和 c 列。每个单元可能包含草或杂草。例如,一个 4 × 5 的花园可能如下所示(空单元格表示草):

你有一台割草机来割掉所有杂草。最初,您拿着割草机站在花园的左上角。即,在单元格 (1, 1) 处。在任何时刻,你都面向某个方向——要么向左,要么向右。最初,你面向右。

在一次移动中,您可以执行以下任一操作:

1) 向您面对的方向移动一个单元格。

- 如果您面向右:从单元格 (r, c) 移动到单元格 (r, c + 1)
- 如果您面向左:从单元格 (r, c) 移动到单元格 (r, c - 1)

- 如果您之前面向右,您将面向左
- 如果您之前面向左,您将面向右

您不得离开花园。如果你和你的割草机站在有杂草的牢房前,杂草就会被割掉(你的方向并不重要)。此动作不计为一次移动。

割掉所有杂草最少需要多少步?

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 150) — 分别是行数和列数。然后跟随 n 行,每行包含 m 个字符——网格的内容。 “G”表示该单元格内有草。 “W”表示该单元格内有杂草。

保证网格的左上角将包含草。

输出

打印一个数字 — 割除所有杂草所需的最少移动次数。

示例

输入 #1

4 5
GWGGW
GGWGG
GWGGG
WGGGG

输出 #1

11

输入 #2

3 3
GWW
WWW
WWG

输出 #2

7

输入 #3

1 1
G

输出 #3

0

注意

对于第一个示例,这是网格初始状态的图片:

一种可能的解决方案是割草,如下图所示: