Дан лабиринт в виде прямоугольной таблицы N×M. Символ '.' — проход, символ '#' — стена. Найдите количество различных путей из левого верхнего угла (0,0) в правый нижний угол (N-1, M-1).
Двигаться можно только
вправо или вниз. Проходить через одну клетку дважды нельзя.
Формат входных данных
Первая строка: два числа N и M — размеры лабиринта (2 ≤ N, M ≤ 5)
Следующие N строк: лабиринт (символы '.' и '#')
Формат выходных данных
Одно число — количество различных путей.
Если путей нет, вывести 0.
Примечание
В тестовом примере существуют два пути
Путь 1: (0,0)→(1,0)→(2,0)→(2,1)→(2,2)
Путь 2: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)
ПОДСКАЗКА:
1. Отмечай посещённые клетки, чтобы не ходить по кругу
2. При откате снимай отметку о посещении
3. Проверяй границы лабиринта и стены
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
...
.#.
...
|
2
|