Update: ниже полное условие задачи
Опять решал задачки на acm, и на региональной тренировке попалась такая задачка. Сам текст задачи писать долго, так как много воды. Поэтому максимально упрощаю.
Вот суть:
Есть таблица RxS, 2<=R,S<=10. Сколько существует путей попасть с верхней левой клетки в нижнюю правую, если в пути клетки не должны повторятся?
Когда разберемся с этим, там есть еще усложнение — задаются клетки, через которые нельзя проходить.
Движение — вверх, вниз, влево, вправо.
В условии клетки через которые можно проходить задаются символом точка ".", а закрытые — решетка "#"
Примеры
…
.#.
Ответ: 1 (есть только один путь, его хорошо видно)
…
…
...
Ответ: 12(ну здесь не так очевидно, но вручную посчитать можно)
Так вот, я написал свой рекурсивный метод, но это простой перебор, которые при R,S > 4 уже очень долго думает. Почитал книги — ничего точного не нашел.
Вот и мучит меня эта задача. Помогите!
Полное условие задачи:
Сантехник Петя был нанят для того, что бы проложить трубу водопровода между двумя точками города. Карту города можно
представить в виде прямоугольника размером RxS, который состоит из квадратных клеток. В некоторых клетках трубу размещать нельзя.
Петя должен соединить с помощью трубы место размещенное над левой верхней клеткой и место под правой нижней клеткой.
Каждую допустимую клетку Петя может либо оставить пустой, либо поместить в нее фрагмент трубы одного из следующих 6 типов.
Найдите количество способов, которыми Петя может построить непрерывную трубу, которая соединяет обозначенные две точки, размещая в клетках имеющиеся у него фрагменты.
Выведите количество способов по модулю 10007
Входные данные:
Первая строчка содержит целые числа R и S (2 <= R,S <= 10), количество строк и столбцов на карте города. В каждой из следующих R строк содержится ровно S символов: "." — если клетка подходит для размещения трубы, и "#" если нет.
Выходные данные:
Количество способов по модулю 10007
Примеры
Input
2 3
…
.#.
Output
1
Input
3 3
…
…
…
Output
12
