Пути по игровому полю с ловушками

В игре герой идёт по прямоугольному полю размером h×w. Он стартует в левом верхнем углу и должен дойти в правый нижний.

За один ход он может:

• перейти на клетку вправо
• или на клетку вниз

Некоторые клетки — ловушки, на них заходить нельзя.

Посчитайте, сколькими способами можно добраться до финиша.

Важно: ответ может не помещаться в 32-битный тип (как на олимпиадах), но гарантированно помещается в 64-битный. В Python это не проблема.

Формат ввода

• В первой строке два целых числа h и w.
• Далее h строк по w символов: . — свободная клетка, # — ловушка.

Гарантируется, что клетки (1,1) и (h,w) — свободные (символ .).

Формат вывода Выведите одно целое число — количество допустимых путей.

Ограничения

• 1 ≤ h ≤ 25
• 1 ≤ w ≤ 25

Пример Ввод:

3 4
....
.#..
....

Вывод:

4

Ключевое наблюдение: чтобы попасть в клетку (i, j), герой может прийти только из двух мест — (i-1, j) сверху или (i, j-1) слева. Значит, число способов добраться до (i, j) зависит только от уже посчитанных соседей.

Это классическое динамическое программирование (ДП): заполняем таблицу слева направо, сверху вниз, и в каждой клетке храним ответ «сколько путей ведёт сюда, не наступая на ловушки».

План:

• Считайте поле в массив строк.
• Создайте dp размером h×w, заполните нулями.
• База: dp[0][0] = 1 (старт свободный).
• Пройдитесь по клеткам в порядке увеличения i, затем j:
• если клетка — ловушка #, то dp[i][j] = 0 и дальше не считаем.
• иначе сложите пути из доступных соседей:
• сверху, если i>0
• слева, если j>0
• мини-сниппет перехода:
• dp[i][j] = (i>0)*dp[i-1][j] + (j>0)*dp[i][j-1]
• Ответ: dp[h-1][w-1].

Почему это работает: любой допустимый путь в (i, j) обязательно заканчивается шагом «вниз» или «вправо», а ловушки просто запрещают состояние.

Сложность: O(h*w) по времени и O(h*w) по памяти (при желании можно ужать до O(w)).

Частая ошибка: забыть обнулить dp на ловушках или неправильно обработать первую строку/первый столбец (там есть только один источник).