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

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

Войти
Регистрация
Восстановить пароль
 
Юлия17071992
0 / 0 / 0
Регистрация: 29.05.2011
Сообщений: 55
#1

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

14.08.2012, 11:11. Просмотров 592. Ответов 3
Метки нет (Все метки)

Узник пытается бежать из замка, который состоит из 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
14.08.2012, 11:11     Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату
Посмотрите здесь:

Программа, которая бы записывала в текстовый файл информацию о всех пакетах, проходящих через сетевую карту C++
найти количество различных маршрутов, ведущих к спасению C++
Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует C++
C++ Программа, определяющая для заданного целочисленного объекта определить количество ведущих единиц старшего его байта
C++ Определить количество ведущих нулей старшего байта short int
Определить количество ведущих единиц C++
программа,позволяющая для заданного целочисленного объекта (int) определить количество ведущих единиц младшей его тетрады C++
C++ Программа должна читать из консоли переменное количество аргументов и выводить их
Вывести время отправления и номера маршрутов, проходящих через данный населенный пункт C++
C++ Программа должна напечатать сумму цифр числа
C++ Пользователь вводит количество звёздочек и количество пробелов, через которые должна выводиться каждая звёздоч
C++ Посчитать количество замкнутых маршрутов, проходящий ровно через четыре различных города

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
14.08.2012, 14:23
  #2

Не по теме:

Цитата Сообщение от Юлия17071992 Посмотреть сообщение
Задачка из городской олимпиады, которая уже прошла, очень хочу узнать как она решается....
- в агусте уже прошла
Думаю это задача может быть описана с помощью алгоритма Дейкстры, в интернете куча ссылок с кодами по этому вопросу...

Юлия17071992
0 / 0 / 0
Регистрация: 29.05.2011
Сообщений: 55
15.08.2012, 10:55  [ТС]     Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату #3
Она по-моему в мае проходила, раньше не было времени эту тему создать
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
15.08.2012, 12:40     Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату #4
найти количество различных маршрутов, ведущих к спасению
Yandex
Объявления
15.08.2012, 12:40     Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату
Ответ Создать тему
Опции темы

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