Люди, помогите, пожалуйста решить задачу(на VB или Qbasic`e)!!!!!!!! Вот её условие:

В прямоугольной таблице n строк и m столбцов (n и m) не превосходят 10. Подсчитать число возможных маршрутов перехода из левой верхней клетки в правую нижнюю, если разрешены перемещения только вниз и вправо и несколько клеток(но не начальная и не конечная) запрещены для посещения.

Пример:
Число строк 3
число столбцов 4
Число клеток, запрещенных для посещения 2
Их координаты:
1,4
3,2
Число маршрутов 6

Если кто сможет решить, то, Please, намыльте мне код!([email protected])

трудновато...
Если бы надо было посчитать кратчайший маршрут, помог бы...

Попробуй полным перебором! Каждый раз смещаясь на одну клетку в сторону от предвидужего маршрута, обходя недоступные клетки!

Задача на графы!

чтобы посчитать количество путей к заданной клетке, можно использовать следующий алгоритм:
пусть f(x,y) - функция, которая вычисляет количество всевозможных путей к клетке (x,y)
тогда:
1. f(0,0)=1
2. если клетка запрещена => f(x,y)=0
3. иначе => f(x,y)=f(x-1,y)+f(x,y-1)

maxim1000, молоток!
Задача не на графы, а на рекурсию, которую так любят преподы. Лично я хотел идти от начальной точки , но а в остальной идея та же. Сам понимаешь было бы не идеальное решение. У тебя можно кое что подправить, а так классно!

1. f(1,1) = 1
2. если (клетка запрещена или x = 0 или y = 0) => f(x,y)=0
3. иначе => f(x,y)=f(x-1,y)+f(x,y-1)

Должно работать.

ну, это алгоритм записан рекурсивно, а для его реализации рекурсию можно обойти
делаем двумерный массив, соответствующий таблице
в каждую клетку записываем количество путей, по которым в нее можно прийти
при этом используем информацию об уже обработанных клетках
сначала можно будет проанализировать только одну клетку - начальную (будет 1)
потом - ту, которая снизу (тоже будет 1)
так заполнится первый столбец
второй столбец:
первая клетка - 1
каждая следующая клетка - верхняя + левая
так по одному столбцу можно будет заполнить всю таблицу
при заполнении последней клетки мы получим ответ

Цитата

В прямоугольной таблице n строк и m столбцов (n и m) не превосходят 10.

Поэтому заморачиваться не стоит и можно оставить рекурсию. Тем более, что не известен размер и

Цитата

делаем двумерный массив, соответствующий таблице

делает процедуру неуникальной.

Цитата

заморачиваться не стоит и можно оставить рекурсию

просто идея пришла из другой области (распознавание речи с использованием динамического программирования), там была похожая ситуация, а время было критично
но в данном конкретном случае полностью согласен

Я когда время критично пишу исключительно на ассемблере (ну и без рекурсии соответственно, тем более, что ее можно часто (но не всегда) очень красиво переделать в псевдо-рекурсию).

Цитата

просто идея пришла из другой области (распознавание речи с использованием динамического программирования), там была похожая ситуация, а время было критично но в данном конкретном случае полностью согласен

Да уж, динамическое программирование весьма гибкая штука, где уж его только не применяли...

Да.... Эта задача - одна из классических задач динамического программирования.

а как создать генератор карт МТУ ??

Вот на ум что пришло:
Можно перемещаться только вверх и вправо? Хех, ну допустим есть поле m на n, то число маршрутов из (0,0) в (m-1, n-1) это ведь биномиальный коэффициент: (m+n - над - m) !!!

Такое решение не требует рекурсии. Если есть какие-то места, которые нельзя посещять, то мы должны знать их "площадь" и тем же методом определить сколько разных ходов через них проходят, отнять их количество от общего и получатся все возможные ходы!

Вот пример: 0 - ход возможен, 1 - препятствие:

00000000
00000000
00111000
00111000
00000000

сколько возможных ходов? Это поле 8 на 5, значит всего: (8+5 - над - 5) = 1287
площадь препятствия: 3 на 2, через него проходит (3+2 - над - 2) = 10 ходов.
Значит всего: 1287-10=1277 !!!