Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Rustam
12 / 12 / 3
Регистрация: 05.09.2009
Сообщений: 440
#1

количество маршрутов, ведущих узника к выходу - C++

12.09.2009, 14:00. Просмотров 644. Ответов 0
Метки нет (Все метки)

Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M×N. Между любыми двумя соседними комнатами есть дверь , однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в M+N-1 комнате, включая начальную и конечную комнату на своем пути, то есть с каждым переходом в соседнюю комнату расстояние до выхода из замка должно уменьшаться. От вас требуется найти количество различных маршрутов, ведущих к спасению.
Формат входных данных

Первая строчка входных данных содержит натуральные числа M и N, не превосходящих 1000. Далее идет план замка в виде M строчек из N символов в каждой. Один символ соответствует одной комнате: если символ равен 1, то в комнату можно попасть, если он равен 0, то комната закрыта. Первоначальное положение узника – левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1).
Формат выходных данных

Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует.

Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2.000.000.000.
Пример

Входные данные
3 5
11111
10101
11111

Выходные данные
3

Входные данные
3 5
11101
10101
10111

Выходные данные
impossible
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.09.2009, 14:00     количество маршрутов, ведущих узника к выходу
Посмотрите здесь:
C++ Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату
Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует C++
найти количество различных маршрутов, ведущих к спасению C++
Определить количество ведущих единиц C++
C++ Определить количество ведущих нулей старшего байта short int
C++ Количество маршрутов
C++ Количество маршрутов с препятствиями
C++ Программа, определяющая для заданного целочисленного объекта определить количество ведущих единиц старшего его байта
программа,позволяющая для заданного целочисленного объекта (int) определить количество ведущих единиц младшей его тетрады C++
C++ Посчитать количество замкнутых маршрутов, проходящий ровно через четыре различных города
C++ Найти количество всевозможных маршрутов от города до города
Вывести путешественников, попавших в лабиринт, к выходу C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru