Попытка сбежать Узник стремится покинуть замок, состоящий из N∗M квадратных комнат, организованных в виде
Попытка сбежать Узник стремится покинуть замок, состоящий из N∗M квадратных комнат, организованных в виде N∗M прямоугольника. Каждая пара соседних комнат соединена дверью, но некоторые из них закрыты и недоступны. Узник начинает свой путь из левой верхней комнаты и должен добраться до правой нижней. Он имеет ограниченное количество времени и может посетить не более N+M−1 комнат на пути. Необходимо определить количество возможных маршрутов к свободе. Входные данные: первая строка содержит натуральные числа N и M.
Даша 66
Задача: Попытка сбежатьДля решения данной задачи нам потребуется использовать динамическое программирование. Мы будем идти от стартовой комнаты в левом верхнем углу к целевой комнате в правом нижнем углу и искать все возможные пути.
1. Создание таблицы
Для хранения количества возможных путей будем использовать таблицу размером N x M, где каждая ячейка table[i][j] будет содержать количество путей от стартовой комнаты до комнаты (i, j).
2. Инициализация значений
- table[0][0] = 1, так как количество путей до стартовой комнаты равно 1.
3. Итеративное заполнение таблицы
Мы начнем заполнять таблицу построчно, идя от верхнего левого угла к нижнему правому.
- Для каждой ячейки table[i][j] будем суммировать количество путей из верхней ячейки и левой ячейки, если они существуют.
- Если встречается закрытая дверь, количество путей до этой комнаты будет равно 0.
4. Получение результата
После заполнения таблицы, искомое количество возможных маршрутов к свободе будет находиться в table[N-1][M-1].
Таким образом, мы можем определить количество возможных маршрутов к свободе для заданных N и M.