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

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

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

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

12.09.2009, 14:00. Просмотров 678. Ответов 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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.09.2009, 14:00
Здравствуйте! Я подобрал для вас темы с ответами на вопрос количество маршрутов, ведущих узника к выходу (C++):

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

Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует - C++
Здравствуйте! Имеем функцию на C++.Помогите исправить ошибки, чтобы выводился правильный результат. Сначало условие, а ниже будет...

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

Определить количество ведущих единиц - C++
здарвствуйте все! помогите пожалуйста с заданиями по мере возможностей: 1) представить программу, позволяющую для заданного...

Определить количество ведущих нулей старшего байта short int - C++
Представить программу, позволяющую для заданного целочисленного объекта short int определить количество ведущих нулей старшего его байта

Количество маршрутов - C++
Доброе утро всем!:) Есть задачка. На картинке показаны шесть квадратов и возможные маршруты их прохождения. НУжно посчитать количество...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.09.2009, 14:00
Привет! Вот еще темы с ответами:

Количество маршрутов с препятствиями - C++
Здравствуйте, вот познаю основы динамического программирование и столкнулся с проблемой во время решения классической задачи "Количество...

Программа, определяющая для заданного целочисленного объекта определить количество ведущих единиц старшего его байта - C++
Здравствуйте, помогите, пожалуйста, выполнить задачу. Нужна программа, позволяющая для заданного целочисленного объекта (int) определить...

программа,позволяющая для заданного целочисленного объекта (int) определить количество ведущих единиц младшей его тетрады - C++
огрооомная просьба помочь: Представить программу, позволяющую для заданного целочисленного объекта (int) определить количество ведущих...

Посчитать количество замкнутых маршрутов, проходящий ровно через четыре различных города - C++
Задача E. Тетрациклофобия Имя входного файла: phobia.in Имя выходного файла: phobia.out Ограничение по времени: 2 секунды ...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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