Codeforces Beta Round 87 (Div. 1 Only) |
---|
Закончено |
У вас есть сад, в котором растет трава и сорняки. Ваш сад представляет собой клетчатое поле размером n × m. Строки пронумерованы от 1 до n сверху вниз, а столбцы — от 1 до m слева направо. Каждая клетка обозначается парой (r, c), где r — номер строки, в которой расположены клетка, а c — номер столбца. Каждая клетка содержит либо траву, либо сорняк. Например, сад размера 4 × 5 может выглядеть следующим образом (пустые клетки обозначают траву):
У вас есть газонокосилка, и вы хотите скосить все сорняки. Изначально вы и ваша газонокосилка находитесь в левом верхнем углу сада, то есть в клетке (1, 1). В каждый момент времени вы смотрите либо направо, либо налево. Изначально вы смотрите направо.
За один ход вы можете сделать одно из двух:
1) Пойти на одну клетку в ту сторону, куда вы смотрите.
Вы не можете выходить за пределы поля. Чтобы скосить сорняк, вы должны оказаться в одной клетке с ним (при этом не имеет значения, в какую сторону вы смотрите). На это действие ход не тратится.
Какое наименьшее количество ходов потребуется, чтобы скосить все сорняки?
В первой строке содержится два целых числа n и m (1 ≤ n, m ≤ 150) — количество строк и столбцов соответственно. Далее следует n строк по m символов в каждой — описание сада. «G» обозначает, что данная клетка содержит траву. «W» обозначает, что данная клетка содержит сорняк.
Гарантируется, что верхняя левая клетка поля содержит траву.
Выведите одно целое число — минимальное количество ходов, которое требуется, чтобы скосить все сорняки.
4 5
GWGGW
GGWGG
GWGGG
WGGGG
11
3 3
GWW
WWW
WWG
7
1 1
G
0
В первом примере начальное состояние поля выглядит следующим образом:
Одно из возможных решений:
Название |
---|