Задача Дремучий лес

В кафе Абу-Даби работает мальчик Джонни. Ему поступил заказ доставить фирменное блюдо этого кафе, Шаурму, в другой конец дремучего леса. Как казалось начальству, Джонни, как опытный доставщик вкусной еды, справится с этим заданием без особых проблем. Но Джонни знал, ему ещё отец рассказывал, что на деревьях Дремучего леса сидят злобные Гуки, расставившие ловушки по всему лесу.

Дремучий лес представляет из себя прямоугольник NxM метров в каждом квадрате 1х1 растёт дерево. Джонни начинает свой бег с любой клетки первой строчки и ему нужно добежать до любой клетки последней строчки.

Джонни поставил себе цель во что бы то ни стало добраться до другого конца леса, как можно быстрее, чтобы Шаурма не успела остыть, поэтому с каждым шагом он должен уменьшать расстояние до последней строчки ровно на 1 метр, при этом за один шаг вперёд Джонни успевает сделать не более одного шага вбок.

К счастью, у Джонни есть хорошие связи, поэтому во время приготовления блюда он узнал на каких деревьях сидят Гуки, а какие деревья являются не деревьями, а ловушками.

Джонни умеет бороться с Гуками, но не знает как выбираться из ловушки.

Также Джонни знает, что если во время очередного шага один из возможных шагов получается в квадратный метр, где растёт дерево, на котором сидят Гуки, они нападут сами, и Джонни придётся идти к их дереву, чтобы с ними расправиться, если таких деревьев несколько, то Джонни может идти к любому из них

Джонни смог найти наиболее оптимальный путь, на котором он встретит наименьшее число Гуков, и теперь ему интересно то, сколько раз он подвергнет шаурму риску быть недоставленной, вступив в бой с целым деревом Гуков?



Формат файла входных данных:

В первой строчке вводятся два числа N, M(3<= N, M <= 1000)

В следующих N строках вводится по M символов, показывающих карту Дремучего леса.

Обычное дерево обозначено символом '.', дерево с Гуками - 'G', а дерево-ловушка - 'X'.



Формат файла выходных данных:

В единственной строке вывести единственное число, со сколькими деревьями Гуков придётся сражаться Джонни.



Имя входного файла : input.txt
Имя выходного файла : output.txt
Ограничение по времени : 1 сек
Ограничение по памяти : 32 Мб

0