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

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

Восстановить пароль Регистрация
 
Юлия17071992
0 / 0 / 0
Регистрация: 29.05.2011
Сообщений: 55
14.08.2012, 11:11     Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату #1
Узник пытается бежать из замка, который состоит из 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
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
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
1920 / 1186 / 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 комнату
Ответ Создать тему
Опции темы

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