| Автор: | А. Жуплев | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 16 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 100 |
Черепаха Тортила любит исследовать лабиринты: она ползает по лабиринту и считает количество вариантов, которыми можно проползти лабиринт с левого нижнего угла в правый верхний.Тортила умеет ползать только вверх, вправо и влево, и в каждую клетку может вползти только один раз.
Недавно черепаха купила компьютер, и хочет по описанию лабиринта быстро рассчитывать количество способов, которыми можно добраться с левого нижнего в правый верхний угол, проползая через каждую клетку не больше одного раза.
Вам нужно написать программу для черепахи Тортилы.
В первой строке входного файла содержатся числа N M
В следующих далее N строчек по M символов содержится описание лабиринта:
В выходном файле должно содержаться единственное число — количество способов, которыми можно добраться с левого нижнего в правый верхний угол, проползая через каждую клетку не больше одного раза.
1 ≤ N, M ≤ 500
Гарантируется, что левый нижний и правый верхний углы лабиринта — пустые клетки
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|
| 3 |
|
|