Paths in the Grid

Динамічне програмування є інструментом для вирішення задач, що набули популярності серед азартних програмістів та авторів коду на сайтах типу TopCoder. Потрібно освоїти підрахунок маршрутів у прямокутній сітці (до прикладу, це може бути квартал міста).

Уявіть карту болотистої місцевості, що представлена прямокутною сіткою:

@ + + + +
+ + + X X
+ X + + +
+ + + X +
+ X + + X
+ + + + $

де X зображає яму (непрохідну клітинку, де людина гарантовано потоне), натомість клітинки + безпечні для проходу.

Герой повинен пройти від верхнього лівого кута (з позначкою @) до нижнього правого (позначений $). Пересуватись він може лише безпечними клітинками, причому з кожної з них він вправі переходити на наступну або праворуч або вниз (згідно карти). Зворотній рух (ліворуч і догори) заборонений: у нашого героя обмежена кількість їди в торбинці.

Потрібно дізнатися, скільки різних маршрутів можна прокласти від одного кута до іншого, згідно поданих правил.

Вхідні дані у першому рядку містять число рядів та стовпців нашої сітки: M та N. Відтак поле сітки складається з M рядків, кожен з яких містить N символів, розділених пробілом. Непрохідні клітинки позначені символом X.
Відповідь повинна містити єдине число - кількість можливих маршрутів.

Результат гарантовано не повинен перевищити 2,000,000,000. Однак можливим є варіант, що маршрутів нема взагалі.

Приклад:

вхідні дані:
6 5
@ + + + +
+ + + X X
+ X + + +
+ + + X +
+ X + + X
+ + + + $

відповідь:
9

На сайті ProjectEuler є версія аналогічної загадки без перешкод: Lattice Paths - радимо насамперед обдумати її, якщо на думку не спадає жодних рішень.